Subsets

Three methods are provided.


//first, use recursive definition of subset 
//iterative version
vector<vector<int> > subsets(vector<int> &S) {
    sort(S.begin(),S.end());
    vector<vector<int> >  ret(1);
    for(int i=0;i<S.size();i++)
    {
        int n=ret.size();
        for(int j=0;j<n;j++){
            ret.push_back(ret[j]);
            ret.back().push_back(S[i]);
        }
    }
    return ret;
}

//recursive version
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>>ret;
        sort(S.begin(),S.end());
        subsetsRe(S,S.size(),ret);
        return ret;
       
    }
//subsetsRe computes the subsets of S[0...num-1] 
    void subsetsRe(vector<int> &S, int num,vector<vector<int>>&ret){
        if(num==0){
            ret.push_back(vector<int>());
            return;
        }
        subsetsRe(S,num-1,ret);
        int n=ret.size();
        for(int i=0;i<n;i++){
            ret.push_back(ret[i]);
            ret.back().push_back(S[num-1]);
        }
    }
};

//another kind of recursion
vector<vector<int> > subsets(vector<int> &S) {
    vector<vector<int> > res(1, vector<int>());//same as vector<vector<int> > res(1);
    sort(S.begin(), S.end());
    vector<int> set;
    int N = S.size();
    for (int l = 1; l <= N; ++l)
        subsetsRe(S, l, 0, set, res);
    return res;
}
//subsetsRe generates all the subsets of length L to be stored in res
void subsetsRe(vector<int> &S, int L, int start, vector<int> &set, vector<vector<int> > &res)
{
    int N = S.size(), M = set.size();
    if (M == L) {
        res.push_back(set);
        return;
    }
    for (int i = start; i <= N - (L - M); ++i) {
        set.push_back(S[i]);
        subsetsRe(S, L, i + 1, set, res);
        set.pop_back();
    }
}



//third one, bit maniputation
vector<vector<int> > subsets(vector<int> &S) {
    sort(S.begin(),S.end());
    vector<vector<int> >  ret;
    int n=S.size();
    for(int i=0;i<1<<n;i++){
        vector<int> temp;
        for(int j=0;j<n;j++){
            if(i&1<<n-j-1)
                temp.push_back(S[j]);
        }
        ret.push_back(temp);
    }
    return ret;
}