跟着灵茶山艾府大佬学习算法思路的day11（并没有在一个月内掌握hot100）
b站链接如下：
回溯算法本质就是遍历多叉树，只要能把问题抽象成树结构，就一定能用回溯算法解决。
“判断 → 不选 → 选（push/递归/pop）” 是子集和组合类回溯的标准模板。排列、搜索、分割等其他回溯题型模板不同，但核心思想都是”试错 → 回退”。
全排列 题目描述：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
1
2
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
思路：
排列问题相比于组合，在排列中的元素的顺序是有区别的。在选择12之后还可以选择21，这是因为排列问题的答案是有序的，而组合问题的答案无序。
组合问题是基于子集问题演化的，而为了避免子集问题的答案无序带来的穷举困难，我们当时手动规定了子集问题的筛选顺序（下标递增等等）。所以即使组合问题的答案无序，我们实际上也手动规定了一个隐含的穷举顺序。
1
2
3
4
5
// 组合：传 start，保证只往后选，避免 [1,2] 和 [2,1] 重复
function combine(nums, start, path) { ... combine(nums, i + 1, ...) ... }
// 排列：不传 start，每轮从头选，但用 used[] 跳过已选的
function permute(nums, used, path) { ... permute(nums, used, ...) ... }
因此对于排列型来说，除了需要维护路径，还需要显式地维护一个组合（在组合型中被start隐式维护）。
对于如何判断剩余可选择数，有几种不同的写法。可以用一个数组记录已选择的数字，用一个集合记录还剩哪些数字可以被选。
这个抽象的集合实际上可以用数组实现，这是更通用的做法。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var permute = function(nums) {
const n = nums.length;
const path = [];
const onPath = [];
const ans = [];
const dfs = (i) => {
if (i === n) {
ans.push(path.slice());
return;
}
for (let j = 0; j < n; j++) {
if (onPath.includes(nums[j])) continue; // 跳过已选的
path.push(nums[j]);
onPath.push(nums[j]);
dfs(i + 1);
onPath.pop();
path.pop();
}
}
dfs(0);
return ans;
};
总结：
时间复杂度的分析是这题的一个重点，根据树状图，可以发现路径长度为n，有n!个叶子结点，所以时间复杂度是o(n*n!)。但显然有部分节点的复杂度会被重复考虑。
如果想更加精确地计算时间复杂度，可以考虑直接计算这棵树有多少节点，知道了节点个数也就知道了递归的次数。
而每层节点的总数，从下至上分别是A33到A30。
最终可以算出节点总数是e*n!（向下取整），这是一个精确的数值。也就是最终精准的复杂度是o(n!)。
最后再考虑上解法中复制路径数组的时间开销，最终是o(n*n!)的时间复杂度。空间复杂度是o(n)。
N 皇后 题目描述：
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
1
2
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
思路：
由于每个皇后一定不同行不同列，所以说明每行每列都恰好有一个皇后，考虑用一个长为n的数组col（下标为行号，元素为列号）来记录皇后位置，那么第i行的皇后就应该在第col[i]列。
如果仅有不同行不同列的要求，通过这个col，我们可以看出同样是一个枚举全排列的问题，但因为要求皇后也不能在同一斜线，所以我们需要进行判断，去掉部分排列。
由于行代表下标，我们是按行插入，只需要保证插入的皇后的左上和右上没有皇后即可。通过行号列号之间的固定数学关系，我们可以限制插入的行为。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
var solveNQueens = function(n) {
const ans = [];
const path = []; // path[i] = j，表示第 i 行的皇后放在第 j 列
const onPath = Array(n).fill(false); // 哪些列已被占用
const diag1 = new Set(); // r - c，主对角线
const diag2 = new Set(); // r + c，副对角线
function dfs(r) {
if (r === n) {
// 根据 path 生成棋盘
ans.push(path.map(j => '.'.repeat(j) + 'Q' + '.'.repeat(n - 1 - j)));
return;
}
for (let c = 0; c < n; c++) {
// 排列约束：这一列不能有皇后
if (onPath[c]) continue;
// 对角线约束：左上和右上不能有皇后
if (diag1.has(r - c)) continue;
if (diag2.has(r + c)) continue;
// 选
path.push(c);
onPath[c] = true;
diag1.add(r - c);
diag2.add(r + c);
dfs(r + 1);
// 恢复现场
path.pop();
onPath[c] = false;
diag1.delete(r - c);
diag2.delete(r + c);
}
}
dfs(0);
return ans;
};
总结：
相较于全排列，n皇后主要有两个额外难点：
- 多维护两条对角线集合，列冲突排列本身已经约束，但对角线冲突是全新的，需要额外发现
r-c和r+c这个规律 - 结果的表示，全排列直接输出 path 就行，N皇后要转换成棋盘字符串
核心难点就是想到用 r±c 判对角线，其余仍然是排列的套路。
最后，对于onPath和其余集合的维护，主要有三种方式：
| 方式 | 查找 | 适用 |
|---|---|---|
静态数组 onPath[c] | O(1) | 值域小且确定（如列号 0~n-1） |
Set onPath.has(c) | O(1) | 值域大或不确定（如 r-c 可能是负数） |
动态数组 includes(c) | O(n) | 都能用，但最慢 |
显然静态数组方式是相对好的。