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
39
40
41
42
43
44

int cmp(int a,int b) {
    return a < b;
}
struct ValNode {
    ValNode():IsExist(false){set_v.clear();}
    vector<vector<int>>set_v;
    bool IsExist;
};
class Solution {
public:
    bool CheckIsExist(vector<int>&item_tmp,vector<vector<int>>&set_v) {
        sort(item_tmp.begin(),item_tmp.end(),cmp);
        for(int i = 0;i < set_v.size();i++) {
            if(item_tmp == set_v[i])return true;
        }
        return false;
    }
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        int max = target;
        ValNode *valnodes = new ValNode[max+1];
        valnodes[0].IsExist = true;
        vector<int>item;
        item.clear();
        valnodes[0].set_v.push_back(item);
        for(int i = 0;i <= target;i++) {
            if(valnodes[i].IsExist) {
                for(int j = 0;j < candidates.size();j++) {
                    if(i + candidates[j] <= target) {
                        valnodes[i+candidates[j]].IsExist = true;
                        for(int k = 0;k < valnodes[i].set_v.size();k++) {
                            vector<int>item_tmp;
                            item_tmp.clear();
                            item_tmp = valnodes[i].set_v[k];
                            item_tmp.push_back(candidates[j]);
                            if(!CheckIsExist(item_tmp,valnodes[i+candidates[j]].set_v))
                                valnodes[i+candidates[j]].set_v.push_back(item_tmp);
                        }
                    }
                }
            }
        }
        return valnodes[max].set_v;
    }
};