题目
带重复元素的子集
给定一个可能具有重复数字的列表，返回其所有可能的子集
样例
如果 S = [1,2,2]，一个可能的答案为：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
注意
- 子集中的每个元素都是非降序的
- 两个子集间的顺序是无关紧要的
- 解集中不能包含重复子集
挑战
你可以同时用递归与非递归的方式解决么？
解题
一个很简单的想法就是在上一题目中增加判断是否已经存在某个子集
class Solution:
"""
@param S: A set of numbers.
@return: A list of lists. All valid subsets.
"""
def subsetsWithDup(self, nums):
# write your code here
res = []
size = len(nums)
nums.sort()
if nums == None or size == 0:
return res
for i in range(1<<size):
lst=[]
n = i
for j in range(size):
if n%2==1:
lst.append(nums[j])
n/=2
if lst not in res:
res.append(lst)
return res
Python Code