题目描述：

难点：集合（数组candidates）有重复元素，但还不能有重复的组合

方法1：回溯

class Solution {
public:
    vector<vector<int>> result;
    vector<int> data;
    void backtrack(vector<int>& candidates, int target,int sum,int StartIndex){
        if(sum==target){
            result.push_back(data);
            return;
        }
        if(sum > target) return;
        for(int i=StartIndex;i<candidates.size();i++){
            data.push_back(candidates[i]);
            sum += candidates[i];
            backtrack(candidates,target,sum,++StartIndex);
            sum -= candidates[i];
            data.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        backtrack(candidates,target,0,0);
        return(result);
    }
};

出错，该题数组中可能出现重复数字，导致后续输出中会出现重复的组合。（组合总和Ⅰ）中为无重复数组

修改：去重，使用unordered_set

class Solution {
public:
    vector<vector<int>> result;
    vector<int> data;
    void backtrack(unordered_set<int> set, int target,int sum,int j){
        if(sum==target){
            result.push_back(data);
            return;
        }
        if(sum > target) return;
        auto index = set.begin();
        for(int i=0;i<j;i++) index++;

        for(auto it=index;it != set.end();it++){
            data.push_back(*it);
            sum += *it;
            backtrack(set,target,sum,++j);
            sum -= *it;
            data.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        unordered_set<int>set;
        for(int i=0;i<candidates.size();i++){
            set.emplace(candidates[i]);
        }
        backtrack(set,target,0,0);
        return(result);
    }
};

出错，把[1,7],[7,1]的重复去了，但是也把[1,1,6]这样的也去了（元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同）

修改：不使用set，先对数组排序，然后相等元素在每一轮中只被选择一次

class Solution {
public:
    vector<vector<int>> result;
    vector<int> data;
    void backtrack(vector<int>& candidates, int target,int sum,int StartIndex){
        if(sum==target){
            result.push_back(data);
            return;
        }
        if(sum > target) return;
        for(int i=StartIndex;i<candidates.size();i++){
            if(i>StartIndex && candidates[i] == candidates[i-1]) continue;
            data.push_back(candidates[i]);
            sum += candidates[i];
            backtrack(candidates,target,sum,i+1); //纵向
            sum -= candidates[i];
            data.pop_back();//回退后下一轮为横向，横向不可以重复，纵向可以
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtrack(candidates,target,0,0);
        return result;
    }
};

注：

• 加上 if(i>StartIndex && candidates[i] == candidates[i-1]) continue;保证横向取时不会取到重复的

• 和39.组合总和的区别 backtrack(candidates,target,sum,i+1)，这里是i+1，每个数字在每个组合中只能使用一次，在组合总和中为i