40. 组合总和 II

used数组去重

使用used进行标记来判断是否重复使用，
used[i-1]=true，代表同一树枝上（即上一层递归去当前层递归元素相同）
used[i-1]=false，代表同一树层（即for循环中当前循环和上一层循环元素相同，此时需要跳过）

class Solution {
public:
    void backtracking(vector<int>& candidates,int target,int startIndex,vector<bool> used)
    {
        if(target==0)
        {
            result.push_back(path);
            return;
        }
        for(int i=startIndex;i<candidates.size()&&target-candidates[i]>=0;i++)
        {
            if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false)continue;
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            path.push_back(candidates[i]);
            used[i]=true;
            backtracking(candidates,target-candidates[i],i+1,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(),false);
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,used);
        return result;
    }
    vector<vector<int>> result;
    vector<int> path;
};

startIndex去重

直接判断for循环过程中，i元素和i-1元素是否相同，相同就跳过

class Solution {
public:
    void backtracking(vector<int>& candidates,int target,int startIndex)
    {
        if(target==0)
        {
            result.push_back(path);
            return;
        }
        for(int i=startIndex;i<candidates.size()&&target-candidates[i]>=0;i++)
        {
            //去重
            if(i>startIndex&&candidates[i]==candidates[i-1])continue;
            path.push_back(candidates[i]);
            backtracking(candidates,target-candidates[i],i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0);
        return result;
    }
    vector<vector<int>> result;
    vector<int> path;
};