BackTrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ret;
vector<int> tmp;
backTrack(nums, ret, 0, tmp);
return ret;
}
private:
void backTrack(vector<int>& nums, vector<vector<int>>& ret, int index, vector<int>& tmp)
{
ret.push_back(tmp);
for(int i = index; i < nums.size(); ++i)
{
tmp.push_back(nums[i]);
backTrack(nums, ret, i + 1, tmp);
tmp.pop_back();
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ret;
ret.push_back({});
for(int i = 0; i < nums.size(); ++i)
{
auto rett = ret;
for(auto tmp : rett)
{
tmp.push_back(nums[i]);
ret.push_back(tmp);
}
}
return ret;
}
};
|
位
一共length长的数组，每个数字看作是二进制0或1，当1时表示选这个数字，0为不选，那么子集一共有2 ^ length长
1627634517255.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int length = 1 << nums.size();
vector<vector<int>> ret;
for(int i = 0; i < length; ++i)
{
vector<int> tmp;
for(int j = 0; j < nums.size(); ++j)
{
if((1 << j) & i)
tmp.push_back(nums[j]);
}
ret.push_back(tmp);
}
return ret;
}
};
|