这题跟之前组合问题不同之处在于给的数组里面的元素是有重复的。
如果按照之前方法处理的话，就会得到重复的集合。
看了卡哥的方法，知道这个去重是是树层去重，横向的；不是树枝去重，纵向的。
这除了和前一个元素比较，还要加一个visit数组。如果前一个元素的visit是false就符合条件。
这个要记得在弹出元素的时候也有，将visit设置为false。
完整代码：
点击查看代码
class Solution {
public:
vector<int>v;
vector<vector<int>>cnt;
void backtracking(vector<int>& candidates, int target,int startflag,vector<bool>visited){
int sum=0;
int sz=v.size();
for(int i=0;i<sz;i++){
sum+=v[i];
}
if(sum>target){return ;}
else if(sum==target){
cnt.push_back(v);
return ;
}
for(int i=startflag;i<candidates.size();i++){
if(i>0&&candidates[i]==candidates[i-1]&&visited[i-1]==false){continue;}
v.push_back(candidates[i]);
visited[i]=true;
backtracking(candidates,target,i+1,visited);
visited[i]=false;
v.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>&candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<bool>visited(candidates.size(),false);
backtracking(candidates,target,0,visited);
return cnt;
}
};