subset II.

subset_II.cpp

class Solution {
public:
/*
 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],
  []
]

*/
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // select 0-N elements from S
        //      sort each combination, and insert to set
        vector<vector<int> > vvInt; 
        int N = S.size();
        int allCnt = 0;
        for(int i=0; i<N; i++)
            allCnt |= 1 << i;       // N digigs of 1
        
        set<vector<int> > svInt;
        for(int i=0; i<=allCnt; i++) {
            vector<int> vInt;
            for(int digit=0; digit<N; digit++) {
                if (i & (1<<digit) )
                    vInt.push_back(S[digit]);
            }
            sort (vInt.begin(), vInt.end());
            svInt.insert(vInt);
        }
        
        set<vector<int> >::iterator it = svInt.begin();
        while( it != svInt.end() ) {
            vvInt.push_back(*it);
            ++it;
        }
        return vvInt;
    }
};