Given a collection of integers that might contain duplicates, S, 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 S = [1,2,2], a solution is:

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

class Solution {public:void subset(vector
     
      
       > &res,vector
       
         &temp,vector
        
          &S,int from){    res.push_back(temp);    for(int i=from;i
         
          from&&S[i]==S[i-1])continue;        temp.push_back(S[i]);        subset(res,temp,S,i+1);        temp.pop_back();    }}    vector
          
           
             > subsetsWithDup(vector
            
              &S) { vector
             
              
               > res; res.clear(); vector
               
                 temp; temp.clear(); int n=S.size(); if(n<1)return res; sort(S.begin(),S.end()); subset(res,temp,S,0); return res; }/* void subset(vector
                
                 
                  > &res,vector
                  
                    &temp,vector
                   
                     &S,int from){ if(from==S.size()) { for(int i=0;i
                    

> subsetsWithDup(vector

&S) { vector

> res; res.clear(); vector

temp; temp.clear(); int n=S.size(); if(n<1)return res; sort(S.begin(),S.end()); subset(res,temp,S,0); return res; }void subset(vector

> &res,vector

&temp,vector

&S,int from, int to,int k){ if(k==0) { for(int i=0;i

to)return; else { temp.push_back(S[from]); subset(res,temp,S,from+1,to,k-1); temp.pop_back(); subset(res,temp,S,from+1,to,k); return; } }} vector

> subsetsWithDup(vector

&S) { vector

> res; res.clear(); vector

temp; temp.clear(); int n=S.size(); sort(S.begin(),S.end()); if(n<1)return res; for(int k=0;k<=n;k++) { subset(res,temp,S,0,n-1,k); } return res; }*/};