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

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

解题思路

这个问题是之前问题Leetcode 78:子集(最详细的解法!!!)的扩展。我们用之前的解法会出现这样的问题,[1,2]会出现两次,因为我们有两个2。最简单的思路就是添加一个判断if tmp not in result,并且我们要对nums排序,为什么?为了避免出现这种情况

1
2
1,4,1
4,1,1

这两种在这个问题中是一种情况,但是在判断[1,4,1]==[4,1,1],两者是不相同的。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return [[]]

nums.sort()
result = self.subsetsWithDup(nums[1:])
return result + [[nums[0]] + s for s in result if [nums[0]] + s not in result]

可想而知,这种做法显然不是最快的。实际上我们这里可以参考 Leetcode 40:组合总和 II(最详细的解法!!!)的回溯法写法,再循环中添加一步判断即可。

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

def _subsetsWithDup(self, nums, index, path, result):
result.append(path.copy())
for i in range(index, len(nums)):
if index < i and nums[i] == nums[i - 1]:# add
continue
self._subsetsWithDup(nums, i + 1, path + [nums[i]], result)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
result = [[]]
for i, _ in enumerate(nums):
if i == 0 or nums[i] != nums[i - 1]:
start = len(result)

end = len(result)
for j in range(end - start, end):
result += [result[j] + [nums[i]]]
return result

我这里的迭代写法使用了一个小trick

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

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