淘宝客网站怎么做推广,织梦手机网站标签调用大全,酒店网站开发程序员,建设银行网站 个人客户端这道题的难点就在于题目所给的集合中有重复的数字#xff0c;我们需要进行去重操作。首先明确去重指的是去重哪一部分。注意并不是对递归的集合去重#xff0c;而是对当前集合的遍历进行去重。这么说可能有点抽象#xff0c;举个例子#xff1a;假设集合为1,1,2,3,4#x…这道题的难点就在于题目所给的集合中有重复的数字我们需要进行去重操作。首先明确去重指的是去重哪一部分。注意并不是对递归的集合去重而是对当前集合的遍历进行去重。这么说可能有点抽象举个例子假设集合为1,1,2,3,4我们第一次选1递归集合时我们仍可以选择第二个1。但是在第一次选第二个1时在往下选就会出现很多与第一次选第一个1时相同的组合。所以在每一层递归函数的for循环中我们需要进行去重。不过我们需要判断这个重复出现的数字是在当前这层递归的for循环中还是在下一层递归的for循环中。于是我们创建了一个数组标识这些集合中的数字是否被使用过如果被使用过说明是在上一层递归中被使用如果没有被使用说明是在当前这一层递归的for循环中。大家可以结合我下面的代码及详细注释理解。
代码及详细注释如下
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint candidates,int target,int sum,int start,vectorint used){//剪枝if(sum target){return;}//终止条件if(sum target){result.push_back(path);return;}for(int i start;i candidates.size();i){//去重if(i 0 candidates[i] candidates[i - 1] used[i - 1] 0){continue;}path.push_back(candidates[i]);sum candidates[i];used[i] 1;backtracking(candidates,target,sum,i 1,used);//回溯path.pop_back();sum - candidates[i];used[i] 0;}return;}vectorvectorint combinationSum2(vectorint candidates, int target) {//创建一个数组该数组下标对应集合中元素的下标表示集合中各个下标对应的数字有没有使用过vectorint used(candidates.size(),0);sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used);return result;}
};
