Subsets II

Backtracking

Problem

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.

For example:

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

Thought Process

• Question is vey similar to the original Subset problem with one difference, there are duplicate numbers in the list

• To handle the duplicate numbers, we will sort the numbers first and skip any numbers that are the same as the previous one

Solution

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        soln = []
        self.helper(sorted(nums), soln, [], 0)
        return soln
    
    def helper(self, nums, soln, subset, index):
        soln.append(list(subset))
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i-1]:
                continue 
            subset.append(nums[i])
            self.helper(nums, soln, subset, i+1)
            subset.pop()
        

Key Points

• To handle the case of some duplicate subsets due to repeated elements, we will sort the input list and in our for loop we will check if nums[i] == nums[i-1] and continue if this is true, because since we already came across that same element previously and recorded the subsets, we don't want to do it again

Time Complexity

• Time: $O(n * 2^n)$

• Space:$O(n * 2^n)$