40. Combination Sum II(再重新看)

要注意去重的模板；
类似于unique subset

if(i != begin && candidates[i] == candidates[i-1]) continue;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> list;
        if(candidates.empty()) return result;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, result, list, target, 0);
        return result;
        
    }
private:
    void dfs(vector<int> candidates, vector<vector<int>>& result, vector<int>& list, int cur, int begin){
        if(cur == 0){
            result.push_back(list);
            return;
        }
        for(int i = begin ; i < candidates.size() && candidates[i] <= cur; i++){
            if(i != begin && candidates[i] == candidates[i-1]) continue;//去重模板
            list.push_back(candidates[i]);
            dfs(candidates, result, list, cur - candidates[i],i+1);//因为这个值不可以重复用，所以要用的是i,
            list.pop_back();
        }
    }
};