View on NeetCode
View on LeetCode

Problem

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Solution

Approach: Backtracking with Duplicate Skipping

This builds on the Subsets backtracking pattern. The for loop picks which value to place at the current position, and the recursion moves to the next position. The for loop is horizontal (sibling choices), and the recursion is vertical (going deeper).

                        []
                /        |        \
             [1]        [2]       [2]  ← skip! same value at same position
            /    \       |
         [1,2]  [1,2]  [2,2]
           |     ↑ skip!
       [1,2,2]

With duplicates in the input, two siblings can have the same value, producing identical subtrees. Sorting the array groups duplicates together, then the skip condition i > start and nums[i] == nums[i-1] catches them: “if a sibling before me already used this same value, skip me.”

Implementation

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()

        def backtrack(start, path):
            result.append(path[:])

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue

                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()

        backtrack(0, [])
        return result

Complexity Analysis

• Time Complexity: O(n * 2^n), where n is the length of nums. Sorting is O(n log n), backtracking generates up to 2^n subsets, each taking O(n) to copy.
• Space Complexity: O(n) for recursion depth (not counting output).

Key Insights

1. For Loop = Siblings, Recursion = Depth: The for loop iterates over candidates for the current position. Each candidate spawns a recursive call that fills the next position. The start parameter prevents going backwards through the sorted array.

2. Skip Condition: i > start means “not the first choice at this level.” Combined with nums[i] == nums[i-1], it skips sibling branches that would produce identical subtrees. Sorting is required so duplicates are adjacent.

3. First Occurrence Always Allowed: At any level, the first duplicate is picked (it might lead to subsets like [1,2,2]). Only the second duplicate at the same level is skipped, because its entire subtree is identical to the first.