题目描述
题目描述
给定一个整数数组,可能包含重复元素。请返回它的所有子集(幂集)。
注意;答案中不能包含相同子集。
样例
样例
输入:[1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
算法1
(递归)
与上题非重复数字的唯一区别:temp加入res时先进行判断是否在res中已经存在,不存在才加入
Python 代码
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res=[]
tmp=[]
nums.sort()
self.dfs(nums,res,tmp,0)
return res
def dfs(self,nums,res,tmp,u):
if tmp[:] not in res:
res.append(tmp[:])
for i in range(u,len(nums)):
# if nums[i]==nums[i-1]:
# continue
tmp.append(nums[i])
self.dfs(nums,res,tmp,i+1)
tmp.pop()