Posted on 2014-01-19 00:59
Uriel 閱讀(198)
評論(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 };