题解 | #加起来和为目标值的组合#

1. 回溯算法。
2. 注意剪枝
3. 注意从下一个选择开始去重，直接进行下一个不重复的元素为止。

class Solution {
public:
        vector<vector<int> > res; // 全局结果变量
        vector<vector<int> > combinationSum2(vector<int> &num, int target) {

        if(!num.size()){
            return vector<vector<int> >(res.begin(),res.end());
        }

        sort(num.begin(),num.end());//排序满足
        vector<int> arr;
        backtracking(num,target,0,0,arr);


        return res;
    }

    void backtracking(vector<int> &num,int target,int curr, int begin, vector<int> &arr){
        if(curr>=target){//剪枝
            if (curr==target) res.push_back(arr);
            return;
        }

        for(int i = begin;i<num.size();i++){

            if(i>begin&&num[i]==num[i-1]) continue;//当前去重

            arr.push_back(num[i]);
            backtracking(num,target,curr+num[i],i+1,arr);
            arr.pop_back();
        }
    }
};