Subsets

Subsets
Given a set of distinct integers, 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,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

 1. (a)
I would like to call it induction
•For n=1, the set of subsets is {{}, {S[0]}}
•For n>1, find the subsets of 1,...,n-1. Make two copies of it. For one of them, add n to each subset.
Then take the union of the two copies.

For example,
•The set of subsets of {S[0]} is {{}, {S[0]}}
•For {S[0], S[1]}, take {{}, {S[0]}}, add S[1],  to each subset to get {{ S[1]}, { S[0], S[1]}} and take the union with {{}, { S[0]}} to get {{}, {S[0]}, {S[1]}, {S[0], S[1]}}
•Repeat till you reach S[n-1] (or finish all the elements)

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res;
        if (S.empty()) return res;
       
        int n = S.size();
        sort(S.begin(),S.end());
        vector<int> empty;
        res.push_back(empty);
       
        for (int i=0; i<n; i++)
        {
            vector<vector<int>> tmp=res;
            for (int j=0; j<tmp.size();j++)
            {
                tmp[j].push_back(S[i]);
            }
           
            for (int j=0; j<tmp.size();j++)
            {
                res.push_back(tmp[j]);
            }
        }
       
        return res;
    }
};


1(b). Same idea, different implementation. 增量构造法 Ref: http://m.blog.csdn.net/blog/mysee1989/39619401

Using vector::back() will simplify the code
http://www.cplusplus.com/reference/vector/vector/back/

  vector<vector<int> > subsets(vector<int> &s) {
               vector<vector<int>> res;
             
               if (s.empty()) return res;
               sort(s.begin(), s.end());
               res.clear();
               res.resize(1);
               int n = s.size();
               for (int i = 0; i<n; i++)
                   {
                       int size = res.size();
                          for (int j = 0; j<size; j++)
                          {
                                 res.push_back(res[j]);
                                 res.back().push_back(s[i]);
                          }
                   }
                    return res;
  }

2. Backtracking with recursion. We need to set a bool vector as the solution vector a
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &s) {
        vector<vector<int>> ret;
        int n=s.size();
        //if (n==0) return ret;
        sort(s.begin(),s.end());
        vector<bool> a(n,false);
        helper(s,a,ret,n,0);
       
        return ret;
    }
   
   
    void helper(vector<int> &s, vector<bool> &a, vector<vector<int>> &r, int n, int k)
    {
        if (k==n)
        {
            //process sol
            vector<int> v;
              for (int j = 0; j<n; j++)
               {
                    if (a[j] == true)
                     v.push_back(s[j]);
                   }
            r.push_back(v);
            return;
        }
        else
        {
            a[k]=true;
            helper(s,a,r,n,k+1);
            a[k]=false;
            helper(s,a,r,n,k+1);
        }
    }
};

3. This is to use an int's bits as a mask for solution vector. If i's position is 1, then choose S[i], otherwise, do not include S[i] in the solution vector.
For example, for n=3 or {1,2,3}, lets assign bits to each outcome  -> First bit to 1 , Second bit to 2 and third bit to 3
Has = 1
No = 0
0) 0 0 0  -> No 3 , No 2 , No 1 = { }
1) 0 0 1  -> No  3 , No 2 ,   Has 1       =  {1 }
2) 0 1 0  -> No 3 ,    Has 2  , No 1 = { 2 }
3) 0 1 1  -> No 3 ,    Has 2 ,      Has 1    = { 1 , 2 }
4) 1 0 0  ->    Has 3      , No  2  , No 1 = { 3 }
5) 1 0 1  ->    Has 3      , No  2  ,     Has 1     = { 1 , 3 }
6) 1 1 0  ->    Has 3      ,    Has 2       , No 1 = { 2 , 3 }
7) 1 1 1  ->    Has 3     ,      Has 2     ,      Has 1     = { 1 , 2 , 3 }

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res;
        if (S.empty()) return res;
       
        sort(S.begin(),S.end());
        int n=S.size();
       
        int numVec = pow(2,n);
       
        for (int i=0; i<numVec; i++)
        {
            vector<int> v;
            for (int j=0; j<n; j++)
            {
                if (i&1<<j)
                    v.push_back(S[j]);
            }
            res.push_back(v);
            v.clear();
        }
      
       return res; 
    }
};