Code & Fun

第27天

今天的题目是Subsets:

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

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

我的做法是用递归的方法去做:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<int>> subsets(vector<int>& nums) {
vector< vector<int> > ret;
vector<int> vec;
ret.push_back(vec);
subsetsIter(ret,nums,vec,0);
return ret;
}

void subsetsIter(vector< vector<int> > &ret,vector<int> &nums,vector<int> now,int beg) {
//if (now.size() == nums.size()) return ;
now.push_back(-1);
auto rbeg = now.rbegin();
for(int i = beg;i < nums.size();i++) {
*rbeg = nums[i];
ret.push_back(now);
subsetsIter(ret,nums,now,i+1);
}
now.pop_back();
}

然后是在dicuss中看到的迭代的方法和利用二进制的方法:

1
2
3
4
5
6
7
8
9
10
11
12
vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> subs(1, vector<int>());
for (int i = 0; i < nums.size(); i++) {
int n = subs.size();
for (int j = 0; j < n; j++) {
subs.push_back(subs[j]);
subs.back().push_back(nums[i]);
}
}
return subs;
}
1
2
3
4
5
6
7
8
9
10
vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(), nums.end());
int num_subset = pow(2, nums.size());
vector<vector<int> > res(num_subset, vector<int>());
for (int i = 0; i < nums.size(); i++)
for (int j = 0; j < num_subset; j++)
if ((j >> i) & 1)
res[j].push_back(nums[i]);
return res;
}

本文首发于Code & Fun