leetcode 90. Subsets II-蒲公英云

leetcode 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
class Solution {
    void select_one(set<pair<set<int>, set<int>>>&candi)
    {
        set<pair<set<int>, set<int>>>newcandi;
        for (set<pair<set<int>, set<int>>>::iterator it
            = candi.begin(); it != candi.end(); it++)
        {
            for (set<int>::iterator it1 = it->second.begin(); it1 != it->second.end(); it1++)
            {
                set<int>sel = it->first;
                set<int>remainindex = it->second;
                sel.insert(*it1);
                remainindex.erase(*it1);
                if (newcandi.find(pair<set<int>, set<int>>(sel, remainindex)) == newcandi.end())
                    newcandi.insert(pair<set<int>, set<int>>(sel, remainindex));
            }
        }
        candi = newcandi; 
    }
    vector<vector<int>>combine(int m, int n)
    {
        vector<vector<int>>ret;
        set<int>index;
        for (int i = 0; i < n; i++)
            index.insert(i);
        set<pair<set<int>,set<int>>>candi;
        set<int>aa;
        candi.insert(pair<set<int>, set<int>>(aa, index));
        while (m-- != 0)
        {
            select_one(candi);
        }
        for (set<pair<set<int>, set<int>>>::iterator it = candi.begin(); it != candi.end(); it++)
        {
            ret.push_back(vector<int>(it->first.begin(), it->first.end()));
        }
        return ret;
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>>result;
        map<int, int>count;
        for (int i = 0; i < nums.size(); i++)
            count[nums[i]]++;
        set<map<int, int>>hist;
        for (int i = 0; i <= nums.size(); i++)
        {
            vector<vector<int>>re = combine(i, nums.size());
            for (int f = 0; f < re.size(); f++)
            {
                vector<int>tt;
                map<int, int>cnt;
                for (int j = 0; j < re[f].size(); j++)
                {
                    tt.push_back(nums[re[f][j]]);
                    cnt[nums[re[f][j]]]++;
                }
                if (hist.find(cnt) == hist.end())
                {
                    hist.insert(cnt);
                    result.push_back(tt);
                }
            }
        }
        return result;
    }
};