Posted on 2014-01-19 00:59
Uriel 阅读(181)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
Subsets
求集合S的所有子集，算是位运算应用的题？DFS也行
1 class Solution {
2 public:
3 vector<vector<int> > subsets(vector<int> &S) {
4 vector<vector<int> > res;
5 sort(S.begin(), S.end());
6 for(int i = 0; i < (1 << S.size()); ++i) {
7 vector<int> tp;
8 for(int j = 0; j < S.size(); ++j) {
9 if((1 << j) & i) tp.push_back(S[j]);
10 }
11 res.push_back(tp);
12 }
13 return res;
14 }
15 };
Subsets II
也是求集合S的所有子集，但是S中可能会有相同元素，所以求的是不重复的子集
位运算枚举然后再判不知道行不行，偷懒用DFS了，然后判重什么的还纠结半天没搞定，参考了下别人的写法
1 class Solution {
2 public:
3 vector<vector<int>> res;
4
5 void DFS(vector<int> &S,vector<int> &tp,int pos) {
6 res.push_back(tp);
7 for(int i = pos; i < S.size(); i++) {
8 while(i != pos && i < S.size() && S[i] == S[i-1]) i++;
9 if(i == S.size()) {
10 return;
11 }
12 tp.push_back(S[i]);
13 DFS(S, tp, i + 1);
14 tp.pop_back();
15 }
16 }
17
18 vector<vector<int> > subsetsWithDup(vector<int> &S) {
19 vector<int> tp;
20 sort(S.begin(), S.end());
21 res.clear();
22 DFS(S, tp, 0);
23 return res;
24 }
25 };