数组中合为target的所有组合

解法1：暴力DFS+剪枝

class Solution {
public:
    vector<vector<int> > ans;
    vector<int> one;
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(), num.end()); //排序
        ans.clear();
        one.clear();
        dfs_find(num, 0, target, 0);
        return ans;
    }
    void dfs_find(vector<int> &num, int k, int target, int cur){
        if(target == cur){
            ans.push_back(one);
            return;
        }
        for(int i = k; i < num.size(); i++){
            if(cur+num[i] > target){  //剪枝，后边的数更大，加上cur会更大于target
                continue;
            }
            if(i>k && num[i]==num[i-1]){  //去重，num[i]用过就不能再用了，但是第一次还是能用
                continue;
            }
            one.push_back(num[i]);        //放入
            dfs_find(num, i+1, target, cur+num[i]);   //递归求解
            one.pop_back();               //恢复
        }
    }
};