39/40/216题

方法：数列中有重复数值的先排序再回溯，若判断当前数组与前一个数组相等则直接跳出本次循环进行下一次循环（continue）

class Solution {
public:
    vector<vector<int>> results;
    vector<int> result;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        combination(candidates,target,0,0);
        return results;
    }
    void combination(vector<int>& candidates, int target,int index,int int_sum){
        if(int_sum>target){
            return;
        }
        if(target==int_sum){
            results.emplace_back(result);
            return;
        }
        for(int i=index;i<candidates.size();i++){
            int_sum+=candidates[i];
            result.emplace_back(candidates[i]);
            combination(candidates,target,i,int_sum);
            int_sum-=candidates[i];
            result.pop_back();
        }

    }
};

class Solution {
public:
    vector<vector<int>> results;
    vector<int> result;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates,target,0);
        return results;
    }
    void dfs(vector<int>& candidates, int target,int index){
        if(target<0){
            return;
        }
        if(target==0){
            results.emplace_back(result);
            return;
        }
        for(int i=index;i<candidates.size();i++){
            if(i > index && candidates[i] == candidates[i-1])
                continue;
            result.emplace_back(candidates[i]);
            dfs(candidates,target-candidates[i],i+1);
            result.pop_back();
        }
    }
};

class Solution {
public:
    vector<vector<int>>results;
    vector<int>result;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k,n,1);
        return results;
    }
    void dfs(int k, int n,int id){
        if(k<0||n<0){
            return;
        }
        if(n==0&&k==0){
            results.emplace_back(result);
            return;
        }
        for(int i=id;i<10;i++){
            result.emplace_back(i);
            n-=i;
            dfs(k-1,n,i+1);
            n+=i;
            result.pop_back();
        }
    }
};