# 90. Subsets II

## 刷题内容

• https://leetcode.com/problems/subsets-ii

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]


## 解题方案

[[],[1]] 是 [1] 的子集合
[[],[1],[2],[1,2]] 是 [1,2] 的子集合，实际上就是1的子集合们加了一个2

****当出现多个重复数字时，应该从 已经拥有了新数字所出现全部次数的list开始加才是合理的****
[[],[1]] 是 [1] 的子集合
[[],[1],[2],[1,2]] 是 [1,2] 的子集合，实际上就是1的子集合们加了一个2
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
] 是 [1,2,2] 的子集和，实际上也就是[1,2]的子集合加了一个2



class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = [[]]
for i in range(len(nums)):
if any(nums[i] in tmp for tmp in res):
res.extend([tmp+[nums[i]] for tmp in res if tmp.count(nums[i]) == i - nums.index(nums[i])])
else:
res.extend([tmp+[nums[i]] for tmp in res])
return res


class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = [[]]
tmp_size = 0
for i in range(len(nums)):
start = tmp_size if i >= 1 and nums[i] == nums[i-1] else 0
tmp_size = len(res)
for j in range(start, tmp_size):
res.append([nums[i]]+res[j])
return res


leetcode第78题一样，DFS, 只不过需要在dfs函数里加一个剪枝的条件，排除掉同样的子集。

class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
def dfs(depth, start, lst):
if lst not in res:
res.append(lst)
if depth == len(nums):
return
for i in range(start, len(nums)):
dfs(depth+1, i+1, lst+[nums[i]])
dfs(0, 0, [])
return res


leetcode第78题一样，backtrack

class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []

def search(cur_lst, idx):
if idx == len(nums):
if cur_lst not in res:
res.append(cur_lst)
return
search(cur_lst + [nums[idx]], idx + 1)
search(cur_lst, idx + 1)

search([], 0)
return res



## References

apachecn/AiLearning