1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

int cmp(int a,int b) {
    return a < b;
}
class Solution {
public:
    vector<vector<int>>ans;
    vector<vector<int>> combinationSum2(vector<int> &num, int target) {
        ans.clear();
        sort(num.begin(),num.end(),cmp);
        vector<int> seq;
        seq.clear();
        addStep(num,0,0,target,seq);
        return ans;
    }
private:
    bool isSeqInAns(vector<int> &seq) {
        for(int i = 0;i < ans.size();i++) {
            if(ans[i] == seq)return false;
        }
        return true;
    }
    void addStep(vector<int> &num,int sum,int k,int target,vector<int> &seq) {
        if(sum == target) {
            if(isSeqInAns(seq))
                ans.push_back(seq);
            return;
        }
        if(k >= num.size()) {
            return ;
        }
        if(sum + num[k] <= target) {
            seq.push_back(num[k]);
            addStep(num,sum+num[k],k+1,target,seq);
            seq.pop_back();
        }
        addStep(num,sum,k+1,target,seq);
    }
};