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

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > result;
        
        //sort s
        for(int i=0;i<S.size();i++)
         for(int j=i+1;j<S.size();j++)
         {
             if(S[i]>S[j])
             {
                 int tmp=S[i];
                 S[i]=S[j];
                 S[j]=tmp;
             }
         }
         
        vector<int> v;
        for(int i=0;i<S.size();i++) v.push_back(0);
        
        gen(result,v,S,0,0,S.size());
        return result;
    }
    void gen(vector<vector<int> >& result,vector<int>& v,vector<int> &S,int dep,int index,int size)
    {
        vector<int> vnew;
        for(int i=0;i<dep;i++)
            vnew.push_back(v[i]);
        result.push_back(vnew);
        
        for(int i=index;i<size;i++)
        {
            v[dep]=S[i];
            gen(result,v,S,dep+1,i+1,size);
        }
    }
};