题目
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
1
2
3
4
5
6
7
8
9
10
11
12
|
输入: nums = [1,2,3]
输出:
[
[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>> recurse(vector<int> &nums) {
vector<vector<int>> vv;
for (int i = 0; i < nums.size(); i++) {
vector<int> copy(nums);
copy.erase(copy.begin() + i);
vv.emplace_back(copy);
auto ret = recurse(copy);
vv.insert(vv.begin(), ret.begin(), ret.end());
}
return vv;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> vv;
vv = recurse(nums);
return vv;
}
|
以题目给的123
为例,我们首先拿到123,之后开始遍历删除其中的字符,进而我们得到了23
、13
、12
这3个数字,之后对他们递归,继续进行该操作,这样我们得到了2
、3
、1
、3
、1
、2
、这6个字符,至此,再加上空集,我们就得到了全部的子集,但这里有个问题,重复的元素有很多,比如在单个字符中,1
、2
、3
各重复了一次,我们需要判重,但问题是该怎么判重?如果用hash表,而C++的set
和map
均不支持对vector
进行hash计算,所以这种实现是不行的。需要换种思路。
在我上面的思路中,是自顶向下的思考,我尝试按照自底向上的思路进行思考。但想了一下,按照我脑中的思考方式,虽然可以很容易做出来,但似乎用程序实现会很麻烦,我不知道该怎么写。。。。。
具体来说,首先我们得到1、2、3,这是长度为1的子集,之后我们我们从中取两个组合形成长度为2的子集,这样得到12、13、23。之后再在长度为2的子集基础上得到长度为3的子集,抛开重复的之后,我们就得到了123。这个组合的过程并不知道该如何实现。
后来无奈看了讨论,发现还是自己的水平不够。在讨论中共给出了3种解法。
递归
虽然自己有考虑自底向上的思考,但思路却错了,这道题实际上是有规律的,而这个规律自己并未想到。
1
2
3
4
5
6
7
8
9
10
|
// 1的子集
[]、[1]
// 新增2的子集为
[2]、[1,2]
// 这样1、2的子集为
[]、[1]、[2]、[1,2]
// 新增3的子集为
[3]、[1,3]、[2,3]、[1,2,3]
// 1、2、3的子集为
[]、[1]、[2]、[1,2]、[3]、[1,3]、[2,3]、[1,2,3]
|
可以看到,新增一个数的子集为之前数据的所有子集之后追加新增的数字。这样我们就可以实现代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
vector<vector<int>> subsets(vector<int>& nums) {
// base case,返回一个空集
if (nums.empty()) return {{}};
// 把最后一个元素拿出来
int n = nums.back();
nums.pop_back();
// 先递归算出前面元素的所有子集
vector<vector<int>> res = subsets(nums);
int size = res.size();
for (int i = 0; i < size; i++) {
// 然后在之前的结果之上追加
res.push_back(res[i]);
res.back().push_back(n);
}
return res;
}
|
回溯
看了别人的回溯实现,我自己是真要哭了。我自己一直在想该如何自底向上实现,但一直没有思路,看了别人的回溯,果然还是自己太蠢。别人的回溯树如下:

对应的回溯实现为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void recurse(vector<int> &nums, int pos, vector<int> track, vector<vector<int>> &vv) {
vv.push_back(track);
for (int i = pos; i < nums.size(); i++) {
track.push_back(nums[i]);
recurse(nums, i + 1, track, vv);
track.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> vv;
vector<int> v;
recurse(nums, 0, v, vv);
return vv;
}
|
思路直接代码体现了,这种思路之前自己也有想过,但是并未跟回溯关联起来,自己一直想的是如何通过多个指针来实现这个过程,但一直感觉使用指针太复杂,因此放弃了。完全想不到这种自底向上的思路竟可用回溯实现。
二进制
以123为例,我们有3位的二进制表示123这3位是否有选择,举例如下:
二进制 |
值 |
000 |
[] |
001 |
[3] |
010 |
[2] |
011 |
[2,3] |
100 |
[1] |
101 |
[1,3] |
110 |
[1,2] |
111 |
[1,2,3] |
我们生成3 bit所有的二进制值,并映射到对应的数组即可。而3bit所有的二进制值生成也很简单,从0依次加到2^3-1即可。
对应的实现如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = []
for i in range(2**n, 2**(n + 1)):
# generate bitmask, from 0..00 to 1..11
bitmask = bin(i)[3:]
# append subset corresponding to that bitmask
output.append([nums[j] for j in range(n) if bitmask[j] == '1'])
return output
|
以上几种的思路的参考自:
- 回溯思想团灭排列、组合、子集问题
- 子集