回溯-剪枝
解题思路
组合问题不允许出现 [2, 3]、[3, 2] 这样的重复组合；
需要从 1…n 的路径上取 k 个数字的组合，例如输入：
n = 4, k = 2可以发现如下递归结构：
- 如果组合里有 1 ，那么需要在 [2, 3, 4] 里再找 1 个数；
- 如果组合里有 2 ，那么需要在 [3, 4] 里再找 1 个数，注意：这里不能再考虑 1，因为包含 1 的组合，在第 1 种情况中已经包含；
需要一个存储组合的数组 path ，保证 path 是升序即可，但不管当前是否符合要求都会循环一次，则很浪费性能，但代码比较好理解；
图解
代码实现
const backtrack = (res: number[][], path: number[], n: number, k: number) => {
if (path.length === k) {
res.push([...path]);
return;
}
for (let i = 1; i <= n; i++) {
// 剪枝：后入的元素必须要 大于 之前的元素，即升序排列
if (path.length && path[path.length - 1] >= i) continue;
path.push(i);
backtrack(res, path, n, k);
path.pop();
}
};
function combine(n: number, k: number): number[][] {
const list = [];
backtrack(list, [], n, k);
return list;
};
回溯-剪枝（优化）
解题思路
组合问题不允许出现 [2, 3]、[3, 2] 这样的重复组合；
需要从 1…n 的路径上取 k 个数字的组合，例如输入：
n = 4, k = 2可以发现如下递归结构：
- 如果组合里有 1 ，那么需要在 [2, 3, 4] 里再找 1 个数；
- 如果组合里有 2 ，那么需要在 [3, 4] 里再找 1 个数，注意：这里不能再考虑 1，因为包含 1 的组合，在第 1 种情况中已经包含；
需要一个存储组合的数组 path ，每一个结点递归地在做同样的事情，区别在于 搜索起点 ，因此需要一个变量 begin ，表示在区间 [begin, n] 里选出若干个数的组合；
剪枝：
- 如果
n = 7, k = 4，从i = 5开始搜索就已经没有意义了，即使把 5 选上，加上后面的数，一共就 3 个候选数，凑不出 4 个数的组合，即i < 5才符合条件；- 那这个 5 是怎么计算出来的呢？这个 5 可以理解为 搜索起点的上边界 ，接下来要选择的元素个数 =
k - path.length；搜索起点的上边界 + 接下来要选择的元素个数 - 1 = n，则 搜索起点的上边界 =n - (k - path.length) + 1；
代码实现
/**
* @param res 结果
* @param begin [begin, n]
* @param path 存储组合的元素
* @param n
* @param k
*/
const backtrack = (res: number[][], begin: number, path: number[], n: number, k: number): void => {
if (path.length === k) {
res.push([...path]);
return;
}
// n=7,k=4，从 5 开始搜索已经没有意义了，所以做了剪枝
for (let j = begin; j <= n - (k - path.length) + 1; j++) {
path.push(j);
backtrack(res, j + 1, path, n, k);
path.pop();
}
}
function combine(n: number, k: number): number[][] {
let list = [];
backtrack(list, 1, [], n, k);
return list;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
进阶技巧🕴️ 聚焦的游离节点导致的内存泄露
上一篇
评论
