组合总和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;
    }
};