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

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) 
    {
        vector<int> keys;
        vector<int> count;
        //count pairs
        for(int i=0;i<S.size();i++)
        {
            int j=0;
            for(j=0;j<keys.size();j++)
                if(keys[j]==S[i]) break;
            if(j==keys.size()) 
            {
                keys.push_back(S[i]);
                count.push_back(1);
            }
            else
            {
                count[j]++;
            }
        }
        //sort pairs
        for(int i=0;i<keys.size();i++)
            for(int j=i+1;j<keys.size();j++)
            if(keys[i]>keys[j])
            {
                int tmp=keys[i];
                keys[i]=keys[j];
                keys[j]=tmp;
                tmp=count[i];
                count[i]=count[j];
                count[j]=tmp;
            }
            
        vector<int> v;
        for(int i=0;i<keys.size();i++) v.push_back(0);
        
        vector<vector<int>> result;
        generate(result,keys,count,v,0);
        return result;
    }
    
    void generate(vector<vector<int>>& result,vector<int>& keys,vector<int>& count,vector<int>& v,int dep)
    {
        //add in the result
        if(dep==keys.size())
        {
            vector<int> newv;
            for(int i=0;i<dep;i++)
                for(int j=0;j<v[i];j++)
                    newv.push_back(keys[i]);
            result.push_back(newv);
            return;
        }
        //generate with next key
        for(int i=0;i<=count[dep];i++)
        {
            v[dep]=i;
            generate(result,keys,count,v,dep+1);
        }
    }
};