-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path78.cpp
37 lines (36 loc) · 1.01 KB
/
78.cpp
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
// dfs_recursion.cpp
class Solution {
void dfs(vector<int>& cur, vector<vector<int>>& res, vector<int>& nums,
int i) {
if (nums.size() == i) {
res.push_back(cur);
return;
}
cur.push_back(nums[i]);
dfs(cur, res, nums, i + 1);
cur.pop_back();
dfs(cur, res, nums, i + 1);
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> cur;
vector<vector<int>> res;
dfs(cur, res, nums, 0);
return res;
}
};
// smart_iteration.cpp
class Solution2 {
public:
vector<vector<int>> subsets(vector<int>& S) {
sort(S.begin(), S.end());
int elem_num = S.size();
int subset_num = pow(2, elem_num);
vector<vector<int>> subset_set(subset_num, vector<int>());
for (int i = 0; i < elem_num; i++)
for (int j = 0; j < subset_num; j++)
if ((j >> i) & 1)
subset_set[j].push_back(S[i]);
return subset_set;
}
};