Subsets II
Created: October 8, 2018 by [lek-tin]
Last updated: October 8, 2018
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],
[]
]
Solution
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()
Iterations shown in:
