Day 38, 77, 78 Combinations, Subsets

Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

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

--------------------------------------------------------
combination, note that in this case, [1,2] and [2,1] are considered the same
we can use a stack instead of vector for vector<int> num

class Solution {
public:
    void comb (vector<vector<int> >&ret, vector<int> num, vector<int> cur, int k) {
        if (k == 0) {
            ret.push_back(cur);
        }else {
            int size = num.size(); 
            for (int i=0;i<size;i++) {
                vector<int> temp = cur;
                temp.push_back(num[0]);
                num.erase(num.begin());
                comb(ret,num,temp,k-1);
            }
        }
    }

    vector<vector<int> > combine(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> num(n);
        for (int i=0;i<n;i++) {
            num[i] = 1+i;
        }
        vector<int> cur;
        vector<vector<int> > ret;
        comb(ret,num,cur,k);
        return ret;
    }
};

Update on Sep-16-2014

class Solution {
public:
    void comb (vector<vector<int> > &rt, vector<int> cur, int n, int k, int index) {
        if (k == 0) {
            rt.push_back(cur);
            return;
        }
        
        for (int i = index; i <= n + 1 - k; i++) {
            vector<int> temp = cur;
            temp.push_back(i);
            comb(rt,temp,n,k - 1,i + 1);
        }
    }

    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > rt;
        vector<int> v;
        comb(rt,v,n,k,1);
        return rt;
    }
};

同subsets的bit operation的方法

class Solution {
public:
    void helper(vector<vector<int>> &rt,vector<int> cur, int n, int k, int index) {
        if (k == 0) {
            rt.push_back(cur);
            return;
        }
        if (k < 0 || index > n) return;
        
        helper(rt,cur,n,k,index + 1);
        cur.push_back(index);
        helper(rt,cur,n,k - 1,index + 1);
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int> > rt;
        vector<int> cur;
        helper(rt,cur,n,k,1);
        
        return rt;
    }
};

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],
  []
]

--------------------------------------------------
Solution #1 recursive, Combination

class Solution {
public:
    void sub (vector<vector<int> > &ret, vector<int> S, vector<int> cur) {
        if (S.size() != 0) {
            int size = S.size();
            for (int i=0;i<size;i++) {
                vector<int> temp = cur;
                temp.push_back(S[0]);
                S.erase(S.begin());
                ret.push_back(temp);
                sub(ret,S,temp);
            }
        }
    }

    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(S.begin(),S.end());
        vector<vector<int> > ret;
        vector<int> cur;
        ret.push_back(cur);
        sub(ret,S,cur);
        return ret;
    }
};

Update on Sep-17-2014

class Solution {
public:
    void sub(vector<vector<int> > &rt, vector<int> cur, vector<int> S, int index) {
        rt.push_back(cur);
        
        for (int i = index; i < S.size(); i++) {
            vector<int> temp = cur;
            temp.push_back(S[i]);
            sub(rt,temp,S,i + 1);
        }
    }

    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(),S.end());
        vector<vector<int> > rt;
        vector<int> v;
        sub(rt,v,S,0);
        
        return rt;
    }
};

Update on Nov-01-2014
Solution #2, Bitmap
For each S it has 2^S.size() subsets and each for loop iteration generates one subset
1 2 3
------
0 0 0
0 0 1
0 1 0
0 1 1
...

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        int numOfSubsets = 1 << S.size();
        sort(S.begin(),S.end());
        vector<vector<int> > rt;
        
        for (int i = 0; i < numOfSubsets; i++) {
            int pos = 0;
            int bitMask = i;
            vector<int> sub;
            
            while (bitMask > 0) {
                if ((bitMask & 1) == 1) {
                    sub.push_back(S[pos]);
                }
                bitMask >>= 1;
                pos++;
            }
            rt.push_back(sub);
        }
        
        return rt;
    }
};

Update on Nov-18-2014
Solution #3 iterative

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > rt;
        vector<int> cur;
        rt.push_back(cur);
        sort(nums.begin(),nums.end());
        
        for (int i = 0; i < nums.size(); i++) {
            vector<vector<int> > temp = rt;
            for (int j = 0; j < temp.size(); j++) {
                temp[j].push_back(nums[i]);
                rt.push_back(temp[j]);
            }
        }
        
        return rt;
    }
};

Update on July-5th-2015
每个数字都可以为 “有” 或 “无”

class Solution {
public:
    void helper(vector<vector<int> > &rt, vector<int> nums, vector<int> cur,int index) {
        if (index == nums.size()) {
            rt.push_back(cur);
            return;
        }
        
        helper(rt,nums,cur,index + 1);
        cur.push_back(nums[index]);
        helper(rt,nums,cur,index + 1);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int> > rt;
        vector<int> cur;
        helper(rt,nums,cur,0);
        
        return rt;
    }
};

ToDo, 以上所有解法要再看一次