只做一种产品的网站,房地产手机网站模板,市场营销七大策略,wordpress 自动发货40. 组合总和 II - 力扣#xff08;LeetCode#xff09;
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意#xff1a…40. 组合总和 II - 力扣LeetCode
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。 样例输入
示例 1: 输入: candidates [10,1,2,7,6,1,5], target 8
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
] 示例 2: 输入: candidates [2,5,2,1,2], target 5,
输出:
[
[1,2,2],
[5]
] 提示:
1 candidates.length 1001 candidates[i] 501 target 30
题解
本题与该题组合总和回溯-CSDN博客的区别在于candidates 候选集合中有重复的元素然而解集中要求不能包含重复的组合因此在求解时要对解集进行去重。
举个例子如下图当candidates [10,1,2,7,6,1,5]target8时显然[1,7]是一个解集但是candidates 存在两个元素1也就是图中指针a和指针c指向的元素如果我们使用回溯法进行遍历势必会出现两个解集[1,7]一个是[a,b]另一个是[b,c]但他们都是解集[1,7]这是不符合题意的。 关于去重
首先我们对candidates 数组进行排序得到如下序列 其次使用回溯法遍历排序后的candidates如果遇到相邻相同的元素candidates[i-1]candidates[i]跳过即可。
那么接下来的问题就转换成了如何在回溯法中模拟这个过程
为方便说明问题我们假定candidates [1,1,2],target3.
如下图所示排序后的candidates如果遇到相邻的相同元素则必有candidates[i-1]candidates[i]但问题在于这种情况在同一树枝下深度的遍历和同一层的横向遍历都会发生而我们要的去重是同一树层的去重也就是在同一层的遍历下遇到candidates[i-1]candidates[i]就跳过。
为区别这两种情况我们使用一个used辅助数组记录每次取数的过程也就是说如果每次取到了一个数就将used的对应位置置为true。 在下图中可以看出在candidates[i] candidates[i - 1]相同的情况下 used[i - 1] true说明同一树枝candidates[i - 1]使用过 used[i - 1] false说明同一树层candidates[i - 1]使用过 故满足我们要求的去重过程可表示为 如果candidates[i] candidates[i - 1] 并且 used[i - 1] false就说明前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。 此时for循环里就应该做continue的操作。 为什么 used[i - 1] false 就是同一树层呢因为同一树层used[i - 1] false 才能表示当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] true说明是进入下一层递归去下一个数所以是树枝上 详细题解过程参考40. 组合总和 II - 力扣LeetCodehttps://leetcode.cn/problems/combination-sum-ii/solutions/857552/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-ig29/ 代码
class Solution {
private:vectorint path;vectorvectorint res;
public:void backing(vectorint candidates,int target,int startIndex,int curSum,vectorbool used){if(curSumtarget) return;if(curSumtarget){res.push_back(path);return;}for(int istartIndex;icandidates.size() curSumcandidates[i]target;i){if(i0 candidates[i-1]candidates[i] used[i-1]false){continue;}else{curSumcandidates[i];used[i]true;path.push_back(candidates[i]);backing(candidates,target,i1,curSum,used);path.pop_back();curSum-candidates[i];used[i]false;}}}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());vectorbool used(candidates.size(),0);backing(candidates,target,0,0,used);return res;}
};
