Leetcode算法条记-（全分列I、全分列II、N皇后）
1. 全分列I题目：给定一个不含重复数字的数组 nums ，返回其 所有可能的全分列 。你可以按恣意次序返回答案。
示例 1：
输入：nums =
输出：[,,,,,]
示例 2：
输入：nums =
输出：[,]
思绪：参考Krahets大神
着实就是高中学的分列组合，对于一个长度为 n 的数组（假设元素互不重复），其分列方案数共有：n! = n×(n−1)×(n−2)…×2×1
根据数组分列的特点，思量深度优先搜索所有分列方案。即通过元素交换，先固定第 1 位元素（ n 种情况）、再固定第 2 位元素（ n−1 种情况）、... 、末了固定第 n 位元素（ 1 种情况）。
https://i-blog.csdnimg.cn/direct/de4bc2512bee478a9c90b710434418ca.png
递归终止条件：
当x = len(nums) – 1时，
x是nums的位置，只要到nums的末了一个位置就停止，（nums范围是,末了一位只有1种情况），将当前组合nums转化为数组并添加到res中，并返回（注意返回到哪里去）。
from typing import List
class Solution:
def permute(self, nums: List) -> List]:
def dfs(x):
if x == len(nums) - 1:
res.append(list(nums)) #将 nums 的副本添加到 res
# res.append(nums.copy()) 也可以
return
for i in range(x, len(nums)):
nums, nums = nums, nums # 交换，将 nums 固定在第 x 位
dfs(x + 1) # 开启固定第 x + 1 位元素
nums, nums = nums, nums # 恢复交换
res = []
dfs(0)
return res 时间复杂度 O(n !n) ： n 为数组 nums 的长度；时间复杂度和数组分列的方案数成线性关系，方案数为 n×(n −1)×(n −2)…×2×1 ，即复杂度为 O(n!) ；必要将当前答案使用 O(n) 的时间复制到答案数组中，相乘得时间复杂度为 O(n×n!) 。
空间复杂度 O(n) ： 全分列的递归深度为 n ，系统累计使用栈空间巨细为 O(n)
打印效果
nums =
result = Solution()
output = result.permute(nums)
print(output) 看不懂递归过程可以参考下图进行单步调试，记住原来nums里是什么，递归后是什么。
https://i-blog.csdnimg.cn/direct/eb0c8810f4754bb7881ad3bb04dabcdd.png
https://i-blog.csdnimg.cn/direct/4d0966837ef24097845c29c1eaa92bdc.png
2. 全分列II
题目：
给定一个可包含重复数字的序列 nums ，按恣意次序 返回所有不重复的全分列
示例 1：
输入：nums =
输出：
[, , ]
示例 2：
输入：nums =
输出：[,,,,,]
思绪：参考Krahets大神
与上一题全分列I的区别是数组中“存在重复元素”。当数组存在重复元素时，分列方案中也存在重复的分列方案。为了清除这些重复方案，需在固定某位元素时，包管“每种元素只在此位固定一次”，即遇到重复元素时不交换，直接跳过，从而将生成重复分列的搜索分支进行“剪枝” 。
from typing import List
class Solution:
def permute(self, nums:List) -> List]:
def dfs(x):
if x == len(nums) - 1:
res.append(nums.copy())
# res.append(list(nums)) 也可以
return
dic = set()
for i in range(x, len(nums)):
if nums in dic: continue
dic.add(nums)
nums, nums = nums, nums
dfs(x+1)
nums, nums = nums, nums
res = []
dfs(0)
return res
打印效果
nums =
result = Solution()
output = result.permute(nums)
print(output)
时间复杂度 O(n !n) ： 与上一题相同 。
空间复杂度 O(n2 ) ： 递归中辅助 Set 累计存储的元素数量最多为 n +( n −1)+...+2+1=( n +1) n /2 ，因此占用 O(n2) 的额外空间。
3. N皇后
题目：
给你一个整数 n ，返回所有不同的 n 皇后问题 的办理方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例1：
https://i-blog.csdnimg.cn/direct/1338d2129b6c4de0865ef02ad97022db.png
示例 2：
输入：n = 1
输出：[["Q"]]
思绪：参考灵神
枚举列号的全分列
可以参考下面图明白
https://i-blog.csdnimg.cn/direct/b54602172ecc4737abf23fd355d02a0d.png
Note：
（1）递归终止条件：所有行都放置了皇后 if r == n:
（2）return 是返回到上一个放置皇后的位置，就是图中上一行的红圈位置
注意这里与全分列终止条件：
全分列中，x是nums的位置，只要到nums的末了一个位置就停止
x == len(nums) - 1时候，nums的位置已经交换完了
但是N皇后中，if r == n:是r刚到第三行，还没完全放完，当r = 4时，才放完第3行
举个栗子（N皇后中）：
假设 n=4，行号为 0, 1, 2, 3。
情况1：if r == n
当 r=4 时，表示已经处置惩罚完所有行（0, 1, 2, 3），所有皇后都已放置完毕。
此时生成棋盘设置并存入 ans。
情况2：if r == n - 1
当 r=3 时，表示正在处置惩罚末了一行（第 3 行），但尚未放置皇后。
如果此时终止递归，会导致末了一行未被处置惩罚，无法生成完整的棋盘设置。
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List]:
ans = []
queens = * n# 皇后放在 (r, queens), # 记录每行皇后的列位置（queens = c）
col = * n
diag1 = * (2 * n - 1)
diag2 = * (2 * n - 1)
def dfs(r: int) -> None:
# 递归终止条件：所有行都放置了皇后
if r == n:
ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
return
"""尝试在当前行(r)的每一列放置皇后"""
for c in range(n):
# 检查当前列和对角线是否被占用
if not col and not diag1 and not diag2:
# 放置皇后并标记
queens = c
col = diag1 = diag2 = True
# 递归处理下一行
dfs(r + 1)
col = diag1 = diag2 = False
dfs(0)# 从第0行开始递归
return ans
打印效果
n = 4
result3 = Solution()
output3 = result3.solveNQueens(n)
print(output3)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]