40. 组合总和 II/C++

与39. 组合总和/C++不同的地方有2点：

1. 要去重
2. 递归时，要用i+1，因为已经使用过candidates[i]了，不能重复使用

以下介绍两种方法去重：
第一种方法是在重复组合生成前就处理掉，这种方法效率较高。先对原数组排序，使得相同元素聚集在一起。如果发现2个相邻元素相同，则直接跳过。

class Solution {
private:
    vector<vector<int>> res;
    vector<int> row;
    
    void combination(vector<int>& candidates, int target,int index) {
        if(target<0)
            return;
        if(target==0){
            res.push_back(row);
            return;
        }
        else{
            for(int i=index;i<candidates.size();++i){
            	//去重，加快运行速度
                if(i>index && candidates[i]==candidates[i-1])
                    continue;
                row.push_back(candidates[i]);
                //此处要用i+1
                combination(candidates,target-candidates[i],i+1);
                row.pop_back();
            }
        }
            
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        combination(candidates,target,0);
        return res;
    }
};

第二种方法，直接生成重复组合，只是将返回的结果数组改成set。利用set无脑去重。这种方法在39. 组合总和/C++基础上很好改

class Solution {
private:
    set<vector<int>> res;
    vector<int> row;
    
    void combination(vector<int>& candidates, int target, int index){
    	//不符合条件，返回
        if(target<0)
            return;
        //符合条件，将row加入res，返回
        if(target==0){
            res.insert(row);
            return;
        }
        else{
        	//从第index个数开始处理，候选解为index及以后的元素
            for(int i=index;i<candidates.size();++i){
                row.push_back(candidates[i]);
                combination(candidates,target-candidates[i],i+1);
                //回溯
                row.pop_back();
            }
        }    
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        res.clear();
        row.clear();
        if(candidates.empty())
            return vector(res.begin(),res.end());
        
        sort(candidates.begin(),candidates.end());
        combination(candidates,target,0);
        return vector<vector<int>>(res.begin(),res.end());
    }
};