力扣第 90 题
题目
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
分析
#1
0078 升级版，区别在于有重复数字，回溯时用 Counter 计数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(i):
if i==len(A):
res.append(path[:])
return
dfs(i+1)
x,w = A[i]
if w:
A[i][1]-=1
path.append(x)
dfs(i)
path.pop()
A[i][1]+=1
res,path = [],[]
A = [[x,w] for x,w in Counter(nums).items()]
dfs(0)
return res
|
29 ms
#2
也可以直接递推。
解答
1
2
3
4
5
6
|
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for x,w in Counter(nums).items():
res += [sub+[x]*k for sub in res for k in range(1,w+1)]
return res
|
37 ms