Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

code1：

class Solution
{
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums)
    {
        if(nums.empty())
            return {{}};

        vector<vector<int>> res;
        vector<int> tmp;
        set<vector<int>> s;
        subsetsWithDup(0,tmp,s,res,nums);
        return res;
    }
private:
    void subsetsWithDup(int start,vector<int> &tmp,set<vector<int>> &s,vector<vector<int>> &res,vector<int>& nums)
    {
        if(start==nums.size())
        {

            vector<int> t(tmp);
            sort(t.begin(),t.end());
            if(s.find(t)==s.end())
            {
                s.insert(t);
                res.push_back(t);
            }
            return;
        }

        tmp.push_back(nums.at(start));
        subsetsWithDup(start+1,tmp,s,res,nums);
        tmp.pop_back();
        subsetsWithDup(start+1,tmp,s,res,nums);

        return ;
    }
};

code2

class Solution
{
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums)
    {
        if(nums.empty())
            return {{}};

        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        vector<int> tmp;
        subsetsWithDup(0,tmp,nums,res);
        return res;
    }
private:
    void subsetsWithDup(int start,vector<int> &tmp,vector<int>& nums,vector<vector<int>> &res)
    {
        res.push_back(tmp);
        for(int i=start;i<nums.size();)
        {
            int first=i++;
            while(i<nums.size()&&nums.at(first)==nums.at(i))
                ++i;
            tmp.push_back(nums.at(first));
            subsetsWithDup(first+1,tmp,nums,res);
            tmp.pop_back();
        }
        return;
    }
};