跟着灵茶山艾府大佬学习算法思路的day10（并没有在一个月内掌握hot100）
b站链接如下：
回溯算法本质就是遍历多叉树，只要能把问题抽象成树结构，就一定能用回溯算法解决。
“判断 → 不选 → 选（push/递归/pop）” 是子集和组合类回溯的标准模板。排列、搜索、分割等其他回溯题型模板不同，但核心思想都是”试错 → 回退”。
组合 题目描述：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
1
2
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 201 <= k <= n
思路：
相比于子集问题，从n个数选固定k个数的组合，可以看着是抽取子集问题中的部分长度固定的子集。
由于题目的范围是有序的，而不是一个任意给定的集合，我们可以考虑从1开始或者从n开始取数来完成这次回溯，那么在提取数的过程中就会遇到一种情况：目前还能被提取的数的数量有可能已经要小于k还需要提取的数的数量，那么对于这种情况，我们是可以跳过的。
为方便这种判断，我们可以从n向前取数，这样k还需要的数字数量和范围内还能取到的数的数值都是同时减小的，不等式的书写会简单一些。
代码：
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
var combine = function(n, k) {
const ans = [];
const path = [];
function dfs(i) {
const d = k - path.length; // 还要选 d 个数
if (d === 0) { // 选够了
ans.push([...path]); // 效果等同path.slice()
return;
}
// 不选 i（前提：跳过 i 后剩下的数还够凑）
if (i > d) {
dfs(i - 1);
}
// 选 i
path.push(i);
dfs(i - 1);
path.pop(); // 恢复现场
}
dfs(n);
return ans;
};
总结：
思路和子集的差别仅在于需要排除部分组合。
组合总和 III 题目描述：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 91 <= n <= 60
思路：
这道题在上道题的基础上增加了数字总和和每个数字只能使用一次的限制，为帮助判断数字总和，我们可以考虑在递归过程中将临时的加和也进行传递记录，并在输出结果和进行数字选择时用加和进行限制。
代码：
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
var combinationSum3 = function(k, n) {
const ans = [];
const path = [];
function dfs(i, sum) { // 需要多传递一个参数来记录加和
const d = k - path.length;
if (d === 0) {
if (sum === n) ans.push([...path]); // 选足数字个数后检测加和是否为n
return;
}
// 不选 i
if (i > d) {
dfs(i - 1, sum);
}
// 选 i
if (sum + i <= n) { // 加和不能大于n
path.push(i);
dfs(i - 1, sum + i);
path.pop();
}
}
dfs(9, 0);
return ans;
总结：
题目模板还是递归（判断，不选，选）的模板，但多一个加和的限制，对模板够熟悉的话这题并不难。