Subsets II

Difficulty: Medium Source: NeetCode

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Subsets (LeetCode 78) — the version without duplicates; this problem extends it
• Backtracking — recursive inclusion/exclusion of elements
• Duplicate handling — the same sort-and-skip trick from Combination Sum II

1. Brute Force

Intuition

Run the standard subset backtracking from Subsets I, but convert every found subset to a sorted tuple and add it to a set to deduplicate. At the end, convert back to a list of lists. It works but the set-based deduplication happens after the fact, so we still explore duplicate branches unnecessarily.

Algorithm

1. Sort nums.
2. Backtrack to generate all subsets.
3. Store each subset as a tuple in a set.
4. Return the deduplicated results.

Solution

def subsetsWithDup_brute(nums):
    nums.sort()
    result_set = set()

    def backtrack(start, current):
        result_set.add(tuple(current))
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return [list(t) for t in result_set]


print(sorted(subsetsWithDup_brute([1, 2, 2])))
# [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
print(sorted(subsetsWithDup_brute([0])))
# [[], [0]]

Complexity

• Time: O(2^n * n) — exponential subsets, hashing each
• Space: O(2^n * n) — storing all subsets in a set

2. Backtracking with Duplicate Skipping

Intuition

Sort nums first so duplicate values are adjacent. During backtracking, at a given recursion level (a given start value), if we pick nums[i] and then try nums[i+1] where nums[i+1] == nums[i], we’d generate the exact same subtree twice. So skip any nums[i] where i > start and nums[i] == nums[i-1]. This is the same skip rule as Combination Sum II — it only prevents picking the same value twice at the same recursion level, not at deeper levels.

Algorithm

1. Sort nums.
2. Define backtrack(start, current).
3. Append a copy of current to results (every state is a valid subset).
4. For i from start to end:
   • If i > start and nums[i] == nums[i-1]: skip (duplicate at same level).
   • Append nums[i], recurse with i + 1, pop.

Solution

def subsetsWithDup(nums):
    nums.sort()
    result = []

    def backtrack(start, current):
        result.append(list(current))
        for i in range(start, len(nums)):
            # skip duplicate elements at the same recursion level
            if i > start and nums[i] == nums[i - 1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result


print(subsetsWithDup([1, 2, 2]))
# [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
print(subsetsWithDup([0]))
# [[], [0]]
print(subsetsWithDup([1, 1, 2, 2]))
# [[], [1], [1, 1], [1, 1, 2], [1, 1, 2, 2], [1, 2], [1, 2, 2], [2], [2, 2]]

Complexity

• Time: O(n * 2^n) — at most 2^n subsets, each costs O(n) to copy
• Space: O(n) — recursion depth

Common Pitfalls

Using i > 0 instead of i > start in the skip condition. This is the most common mistake in this problem. The check i > start means “we’re not the first element being considered at this recursion level.” Using i > 0 would incorrectly skip valid deeper picks — for example, it would prevent [1, 2, 2] from being generated because it would skip the second 2 even at a deeper recursion level where it’s valid.

Forgetting to sort. The skip condition relies on duplicates being adjacent. Without sorting, [2, 1, 2] would not be caught and you’d generate duplicate subsets.

Not appending before the loop. The result.append(list(current)) line must come before the for loop, not inside it. Every state — including the empty set — is a valid subset.