[LeetCode]Subsets

原题链接：http://oj.leetcode.com/problems/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],
  []
]

题解：

　　用一个标志数组来决定当前元素选还是不选，递归实现。

　　这题是不含重复元素的子集生成，加强版本是集合中含有重复元素，见http://www.cnblogs.com/codershell/p/3621687.html，

　　我在《子集问题（寻找给定集合的所有子集）》一文中详细分析了子集问题，具体解释不再赘述。

 1 class Solution {
 2 public:
 3     void ss(vector<vector<int> > &vv,int* flag,int n, vector<int> &S, int cur){
 4         if(cur == n){
 5             vector<int> v;
 6             for(int i = 0; i < cur; i++)
 7                 if(flag[i])
 8                     v.push_back(S[i]);
 9             sort(v.begin(), v.end());
10             vv.push_back(v);
11             return;
12         }
13         
14         flag[cur] = 1;                                // 选第 cur 个元素
15         ss(vv,flag,n, S, cur+1);
16         flag[cur] = 0;                                // 不选第 cur 个元素
17         ss(vv,flag,n, S, cur+1);
18     }
19     vector<vector<int> > subsets(vector<int> &S) {
20         int *flag = (int *)malloc(sizeof(int) * S.size()) ;
21         
22         vector <vector<int>> array;
23         ss(array,flag,S.size(),S,0);
24         free(flag);
25         return array;
26     }
27 };

View Code