回溯
解题思路
由题干可知：输入集合 [2,3,6,7] 中的元素可以被无限次重复选取，子集是不区分元素顺序的，但是不可以是同一个集合， [2,3] 和 [3,2] 就是同一个子集；
比较子集（数组）的异同非常耗时，需要先 排序数组 ，再比较数组中每个元素的异同，
重复子集剪枝：
- 分支 1：如果第一轮选择了 2 ，第二轮选择了 3 ，则记为 [2,3,XX]；
- 分支 2：如果第一轮选择了 3 ，第二轮选择了 2 ，则记为 [3,2,XX] ，那这样就会出现重复集合，第二轮应该跳过 2，从 3 开始；
解决步骤二的问题，可以定义一个 begin 索引，每次递归传入 begin 索引，这样就可以跳过前面的索引，避免重复集合；
集合元素剪枝：如果集合元素 大于 了 target ，那当前元素没必要放入 path 中参与计算了；
图解
代码实现
/**
* @param {* number[][]} res
* @param {* number} begin
* @param {* number[]} candidates
* @param {* number} target
* @param {* number[]} path
* @returns
*/
const backtrace = (res, begin, candidates, target, path) => {
// 剪枝1：如果 target 已经小于 0，没有必要再继续了
if (target < 0) return;
if (target === 0) {
res.push([...path]);
return;
}
for (let i = begin; i < candidates.length; i++) {
let num = candidates[i];
// 剪枝2：如果当前元素 大于 target，则当前元素没必要入栈了
if (num > target) continue;
path.push(num);
target -= num;
// 由于元素可以重复使用，则里传入的 inx 为 i
backtrace(res, i, candidates, target, path);
path.pop();
target += num;
}
}
var combinationSum = function (candidates, target) {
let list = [];
candidates.sort();
backtrace(list, 0, candidates, target, []);
return list;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 77. 组合
上一篇
评论
