Subsets

Subsets

Description:

Given a set of distinct integers, return all possible subsets.

Notice:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

Example:

If S = [1,2,3], a solution is:
[
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
]

分析：

类似于组合数，就是求Cnr, r = 0,1,2…n。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int> &nums) {
    	// write your code here
    	int n = nums.size();
    	vector<vector<int> > allSubsets;
    	
    	sort(nums.begin(), nums.end());
    	for (int i = 1; i <= n; i++) {
    	    vector<vector<int> > combination = getCombinations(n, i);
    	    
    	    for (int j = 0; j < combination.size(); j++) {
    	        vector<int> tem;
    	        for (int k = 0; k < combination[j].size(); k++) {
    	            tem.push_back(nums[combination[j][k]]);
    	        }
    	        //sort(tem.begin(), tem.end());
    	        allSubsets.push_back(tem);
    	    }
    	}
    	allSubsets.push_back(vector<int>());
    	
    	return allSubsets;
    }
    
    vector<vector<int> > getCombinations(int n, int r) {
        vector<vector<int> > combination;
        vector<bool> v(n);
        fill(v.begin(), v.begin() + r, true);
        
        do {
            vector<int> tem;
            for (int i = 0; i < n; i++) {
                if (v[i]) {
                    tem.push_back(i);
                }
            }
            
            if (!tem.empty()) combination.push_back(tem);
        } while(prev_permutation(v.begin(), v.end()));
        
        return combination;
    }
};