Leetcode 78:子集(最详细的解法!!!)

给定一组不含重复元素的整数数组 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],
[]
]

解题思路

这个问题通过递归可以很快的解决,我们只要知道了subsets(nums[1:]),那么我们只要将nums[0]添加到每个子集的前面形成新的子集,然后将新的子集添加到result中即可。

1
2
3
4
5
6
7
8
9
10
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return [[]]
result = self.subsets(nums[1:])
return result + [[nums[0]] + s for s in result]

这个问题我们也可以通过回溯法来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = list()
self._subsets(nums, 0, list(), result)
return result

def _subsets(self, nums, index, path, result):
result.append(path.copy())
for i in range(index, len(nums)):
self._subsets(nums, i + 1, path + [nums[i]], result)

很多人很难理解为什么上面这种写法是回溯法,其实我们将pushpop的过程合到了一块,我在之前的一些问题中也没说明,所以我在此解释一下。

1
self._subsets(nums, i + 1, path + [nums[i]], result)

可以将它分开写成

1
2
3
path.append(nums[i])
self._subsets(nums, i + 1, path, result)
path.pop()

同样的,对于递归可以解决的问题,我们都应该思考是不是可以通过迭代解决。

1
2
3
4
5
6
7
8
9
10
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = [[]]
for num in nums:
result += [item+[num] for item in result]
return result

非常的简洁。最后介绍一种hacker的编码

1
2
3
4
5
6
7
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
return [[nums[j] for j in range(len(nums)) if i>>j&1] for i in range(2**len(nums))]

我们通过for i in range(2**len(nums))建立一组mask,以题目中的例子为例

1
2
3
4
5
6
7
8
00000000
00000001
00000010
00000011
00000100
00000101
00000110
00000111

然后我们通过对mask中的每个编码移位,并且和1进行&操作,如果为true,那么将nums[j]添加到result中。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!