[Leetcode] Subsets 1 ^& 2

Subsets
Apr 18 '12
6226/16269
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],
  []
]

 

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > res;
        int n = S.size();
        for (int i = 0; i <= n; i++) {
            vector<int> a;
        	gen(res, S, i, 0, a);
        }
        return res;
    }

    void gen(vector<vector<int> >& res, const vector<int>& s, int n, int cur, vector<int> &a) {
    	if (a.size() == n) {
    		res.push_back(a);
    		return;
    	}
        if (cur == s.size()) return;

    	gen(res, s, n, cur+1, a);
    	
    	a.push_back(s[cur]);
    	gen(res, s, n, cur+1, a);
    	a.pop_back();
    }
};

 

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > res;
        vector<int> a;
        gen(res, S, 0, a);
        return res;
    }

    void gen(vector<vector<int> >& res, const vector<int>& s,  int cur, vector<int> &a) {
    	if (cur == s.size()) {
        	res.push_back(a);
    		return;
    	}
    	gen(res, s, cur+1, a);
    	
    	a.push_back(s[cur]);
    	gen(res, s, cur+1, a);
    	a.pop_back();
    }
};

 
Subsets II
Jun 25 '12
4769/13419
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],
  []
]

 

class Solution {
public:
    void gen(vector<vector<int> >& res, const vector<int>& s,  int cur, vector<int> &a) {
        if (cur == s.size()) {
        	res.push_back(a);
    		return;
    	}
        int end = cur;
        while (end < s.size() && s[end] == s[cur]) end++;
    	gen(res, s, end, a);
    	
    	for (int i = cur; i < end; i++) {
    	   a.push_back(s[cur]);
           gen(res, s, end, a);
        }
        while (end-- != cur) a.pop_back();
    }

    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > res;
        vector<int> a;
        gen(res, S, 0, a);
        return res;
    }
};