回溯
解题思路
由题干可知：输入集合 [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 中参与计算了；
重复元素剪枝：如果在 begin 索引之后，该元素与左边元素相等（排序后重复元素相邻），说明该搜索分支重复，直接跳过；
代码实现
const backtrace = (res, candidates, target, path, begin) => {
if (target === 0) {
res.push([...path]);
return;
}
for (let i = begin; i < candidates.length; i++) {
let num = candidates[i];
if (target < 0) continue;
if (target < num) continue;
// 如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
if (i > begin && num == candidates[i - 1]) continue;
path.push(num);
target -= num;
backtrace(res, candidates, target, path, i + 1);
path.pop();
target += num;
}
}
var combinationSum2 = function (candidates, target) {
let list = [];
candidates.sort();
backtrace(list, candidates, target, [], 0);
return list;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
进阶技巧🕴️ 封装弹窗组件的正确姿势
上一篇
评论
