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
45
46
47

int cmp(int a,int b) {
    return a < b;
}
class Solution {
public:
    bool CheckIn(vector<int> item1,vector<int> item2) {
        if(item1.size() != item2.size())return false;
        for(int i = 0;i < item1.size();i++) {
            if(item1[i] != item2[i])return false;
        }
        return true;
    }
    void AddItemStep(int i,int k,vector<int>&S,vector<vector<int>>&ans,vector<int>&item) {
        if(item.size() == k) {
            for(int i = ans.size()-1;i >= 0&&item.size() == ans[i].size();i--) {
                if(CheckIn(item,ans[i]) == true)return;
            }
            ans.push_back(item);
            return;
        }
        else {
            if(i >= S.size())return;
            item.push_back(S[i]);
            AddItemStep(i+1,k,S,ans,item);
            item.pop_back();
            AddItemStep(i+1,k,S,ans,item);
        }
    }
    void AddItem(int k,vector<int> &S,vector<vector<int>>&ans) {
        int i = 0;
        vector<int> item;
        item.clear();
        AddItemStep(i,k,S,ans,item);
    }
    vector<vector<int>> subsetsWithDup(vector<int> &S) {
        sort(S.begin(),S.end(),cmp);
        vector<vector<int>>ans;
        ans.clear();
        vector<int>item;
        item.clear();
        ans.push_back(item);
        for(int i = 1;i <= S.size();i++) {
            AddItem(i,S,ans);
        }
        return ans;
    }
};