Unique Subsets

Given a list of numbers that may has duplicate numbers, return all possible subsets

Note

Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.

Example

If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

 
class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
      vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int>> output;
        sort(S.begin(), S.end());
        int lastRoundCount = 1;
        
        output.push_back(vector<int>());
        for(int i = 0; i < S.size(); i++) {
            int count  = 0;
            
            int t = output.size();
            if (i > 0 && S[i] == S[i-1]) 
                t = lastRoundCount;
            
            int n = output.size();
            for(int j = n-1; j >= n-t; j--) {
                vector<int> current = output[j];
                current.push_back(S[i]);
                output.push_back(current); 
                count++;
           }
           
           lastRoundCount = count;
        }
        
        return output;
    }
};

class Solution {
public:
   void DFS(vector<int> &S, int current, vector<int> &tmp, vector<vector<int> > &ans) {
        for(int i = current; i < S.size(); )  {
           tmp.push_back(S[i]);
           ans.push_back(tmp);
           DFS(S, i + 1, tmp, ans);
           tmp.pop_back();
           
           ++i;
           while(i<S.size() && S[i] == S[i-1])
           ++i;
        }
    }
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> >  ans;
        sort(S.begin(), S.end());
        vector<int> tmp;
        DFS(S, 0, tmp, ans);
        ans.push_back(vector<int>(0));
        return ans;
    }
}; 

 
class Solution {
public:
    void helper2(vector<int> &S, int k, int current, vector<int> &tmp, vector<vector<int> > &ans) {
        if (k == 0) {
            ans.push_back(tmp);
            return;
        }
        
        for(int i = current; i <= S.size()-k; )  {
           tmp.push_back(S[i]);
           helper2(S, k-1, i + 1, tmp, ans);
           tmp.pop_back();
           i++;
           while(i < S.size() && S[i] == S[i-1])
            i++;
        }
    }
   
    void helper(vector<int> &S, int k, vector<vector<int> > &ans) {
        vector<int> tmp;
        helper2(S, k, 0, tmp, ans);
    }
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> >  ans;
        sort(S.begin(), S.end());
        for(int i = 0; i <= S.size(); i++) {
            helper(S, i, ans);
        }
        return ans;
    }
};