leetcode 90. Subsets II

╰+攻爆jí腚メ 2022-08-21 03:11 175阅读 0赞

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;
    	}
    };

超时不可避免