组合总和II(力扣40)

这道题的难点就在于题目所给的集合中有重复的数字，我们需要进行去重操作。首先明确去重指的是去重哪一部分。注意并不是对递归的集合去重，而是对当前集合的遍历进行去重。这么说可能有点抽象，举个例子：假设集合为1,1,2,3,4，我们第一次选1，递归集合时，我们仍可以选择第二个1。但是在第一次选第二个1时，在往下选，就会出现很多与第一次选第一个1时相同的组合。所以在每一层递归函数的for循环中我们需要进行去重。不过，我们需要判断这个重复出现的数字是在当前这层递归的for循环中还是在下一层递归的for循环中。于是，我们创建了一个数组，标识这些集合中的数字是否被使用过，如果被使用过，说明是在上一层递归中被使用，如果没有被使用，说明是在当前这一层递归的for循环中。大家可以结合我下面的代码及详细注释理解。

代码及详细注释如下：

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& candidates,int target,int sum,int start,vector<int>& 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;}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {//创建一个数组，该数组下标对应集合中元素的下标，表示集合中各个下标对应的数字有没有使用过vector<int> used(candidates.size(),0);sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0,used);return result;}
};