Subsets II
- 1 min read
- LC-Medium
- Backtracking
3 years ago
Solution
-
Similar to Subsets, but here, we have duplicate numbers, unlike in Subsets I.
-
We solve this using a similar concept to what we saw in Combination Sum II
-
See the image above. If we solve the problem like Subsets I, we'll end up with duplicates.
-
To mitigate this, we have to make sure that if we choose to include a number in the left subtree, that number should not be included at all in the right subtree.
-
To do this, sort the array. This way, we can skip duplicate numbers.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
def dfs(i, sub):
if i == len(nums):
ans.append(sub)
return
dfs(i + 1, sub + [nums[i]])
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
dfs(i + 1, sub)
dfs(0, [])
return ans