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

class Solution {
private:
    int cur_num = 0;
    vector<int> cur_path;
    vector<vector<int>> res;
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        int n = num.size();
        vector<int> vis(n, 0);
        dfs(num, vis, target, 0);
        return res;
    }
    
    void dfs(vector<int> &num, vector<int> &vis, int target, int cur_i){
        if(cur_num == target){
            res.push_back(cur_path);
            return;
        }
        if(cur_num > target){
            return;
        }
        
        for(int i=cur_i; i<num.size(); i++){
            if(vis[i] == 1){
                continue;
            }
            if(i>0 && num[i] == num[i-1] && vis[i-1] == 0){
                continue;
            }
            cur_num += num[i];
            cur_path.push_back(num[i]);
            vis[i] = 1;
            dfs(num, vis, target, i+1);
            cur_num -= num[i];
            vis[i] = 0;
            cur_path.pop_back();
        }
        
    }
    
};