78. Subsets
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Solution: Recursive
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
subsets = []
subset = []
def dfs(start):
subsets.append(subset[:])
for idx in xrange(start, len(nums)):
if idx > start and nums[idx] == nums[idx - 1]:
continue
subset.append(nums[idx])
dfs(idx + 1)
subset.pop()
dfs(0)
return subsets
Solution: Iterative
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
pre = None
start = 0
subsets = [[]]
for num in nums:
idx = start if num == pre else 0
start = len(subsets)
for subset in subsets[idx:]:
subsets.append(subset + [num])
pre = num
return subsets