title | description | authors | tags | categories | date | draft | archive | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subsets II |
Some description ... |
|
|
|
2018-10-08 13:04:14 -0700 |
false |
false |
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Time: O(n * 2^n)
Space: O(n * 2^n)
keep all the subsets of length N
, since each of N
elements could be present or absent.
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
results = []
subset = []
# Edge case 1
if nums == None:
return results
# Edge case 2
if len(nums) == 0:
results.append([])
return results
# Sort nums in ascending order
nums.sort()
# start recursion
self.dfs(0, subset, nums, results)
return results
def dfs(self, startIndex, subset, nums, results):
# Recursion exit condition met
# add a copy of the current subset
results.append(subset[:])
# Entering the next recursion level
for i in range(startIndex, len(nums)):
# Skip duplicate
if (i>=0 and i != startIndex and nums[i] == nums[i-1]):
continue
# add a new number to the current subset
# [1] -> [1,2]
subset.append(nums[i])
# find all subsets to append to [1,2]
self.dfs(i+1, subset, nums, results)
# backtrack by removing 2 from subset: [1,2].
subset.pop()