Subsets II: Backtracking Without Duplicate Subsets

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.

This is LeetCode 90: Subsets II, and it builds directly on Subsets. The twist is that nums can contain duplicate values. For example, [1, 2, 2] should produce [[], [1], [1,2], [1,2,2], [2], [2,2]], not the 8 subsets you would get if every element were unique. Without careful handling, your backtracking will generate duplicate subsets like two copies of [2]. The fix is a single guard clause that skips same-level duplicates after sorting.

Why this problem matters

Subsets II teaches you how to combine two techniques that show up together in many backtracking problems: sorting the input and skipping same-level duplicates. In Subsets, all elements are unique, so duplicates never arise. In Combination Sum II, the same deduplication technique appears but with an additional target-sum constraint layered on top. Subsets II isolates the duplicate-skipping pattern in its purest form, with no target to track and no pruning by value. That makes it the cleanest place to learn the technique.

The pattern you learn here transfers directly. Any backtracking problem where the input contains repeated values and the output must be unique will use the same if i > start and nums[i] == nums[i - 1]: continue guard. Once you can write it from memory, you can apply it to Combination Sum II, Permutations II, and similar problems without rethinking the deduplication logic.

The key insight

Sort the array first. Then, when iterating over choices at a given recursion level, skip any element that equals the previous element at that same level. The check is: if nums[i] == nums[i - 1] and i > start, skip nums[i].

Why does this work? Consider sorted input [1, 2, 2]. At the root level, you try 2 at index 1. That recursive call explores everything reachable by starting with that 2, including [2, 2]. When you return to the root level and reach the second 2 at index 2, every subset it would produce is a subset of what the first 2 already covered. So you skip it.

The critical distinction: the second 2 is only skipped when it appears at the same recursion level as the first 2. At a deeper level, using both 2s is fine because they represent different positions in the recursion tree. That is why [2, 2] is valid but a second standalone [2] is not.

The algorithm works like this:

1. Sort nums.
2. Start with an empty subset, start index 0.
3. Record the current subset (every node in the tree is valid).
4. For each element from the start index onward:
   • If i > start and nums[i] == nums[i - 1], continue (skip same-level duplicate).
   • Otherwise, choose the element (append), explore (recurse with i + 1), and unchoose (pop).

The backtracking solution

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []

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

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

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

    backtrack(0, [])
    return result

Let's break this down.

The outer function sorts nums. Sorting is essential, not optional. Without it, duplicate values are scattered and you cannot detect same-level duplicates by comparing adjacent elements.

Inside backtrack, the very first thing is result.append(current[:]). Unlike Combination Sum II where you only record when a target is reached, in Subsets II every partial subset is valid. You record at every node in the recursion tree, not just at leaves.

The for loop iterates from start to the end. One guard clause appears before the choose step: if i > start and nums[i] == nums[i - 1], skip. The condition i > start is important. At index start, you always try the element (it is the first candidate at this recursion level). Only when i has moved past start do you check for a duplicate.

After the guard, you append the element (choose), recurse with i + 1 (explore elements after it), and pop it off (unchoose). Passing i + 1 ensures you never reconsider elements at earlier indices.

Visual walkthrough

Let's trace through the algorithm with nums = [2, 1, 2]. After sorting, the array becomes [1, 2, 2]. Watch how the duplicate-skipping rule prevents the second 2 from creating redundant branches at each recursion level.

The key moments are Steps 5 and 8. In Step 5, when the loop at [1] reaches index 2, nums[2] == nums[1] (both 2) and 2 > start (1). The algorithm skips it, preventing a second [1, 2]. In Step 8, the same check at the root level prevents a second [2]. Both skips are necessary for a correct result.

Notice that [2, 2] is still valid. The two 2s come from different recursion levels: the first 2 is chosen at the root level (index 1), and the second 2 is chosen one level deeper (index 2). The skip rule only blocks duplicates at the same level.

Complexity analysis

Time is O(n * 2^n) in the worst case. When all elements are unique, there are 2^n subsets and copying each takes up to O(n). Sorting adds O(n log n), which is dominated by the exponential backtracking. When duplicates exist, the actual number of subsets is smaller, but the upper bound remains O(n * 2^n).

Space is O(n * 2^n) for storing all subsets in the result. The recursion stack uses O(n) additional space (maximum depth equals the length of nums). If you exclude the output, the extra space is just O(n).

The building blocks

This problem is built on two core reusable pieces that CodeBricks drills independently.

Sorted backtracking (choose-explore-unchoose with sorted input)

The same skeleton that powers Subsets, Combination Sum, and Combination Sum II:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)
        backtrack(state)
        undo_choice(choice)

In Subsets II, make_choice is current.append(nums[i]). The recursion uses i + 1 to avoid revisiting earlier elements. undo_choice is current.pop(). Sorting the input before calling backtrack groups duplicate values together so the skip guard can detect them.

Same-level duplicate skipping

The pattern for avoiding duplicate results when the input contains repeated values:

if i > start and nums[i] == nums[i - 1]:
    continue

This guard appears in any backtracking problem where the input has duplicates and the output must be unique. The same technique applies to Combination Sum II (LeetCode 40) and Permutations II (LeetCode 47). The key is that i > start ensures you only skip when you have already processed an identical value at the current recursion level.

Edge cases

Before submitting, check these:

• All same elements: nums = [2, 2, 2]. Should return [[], [2], [2,2], [2,2,2]]. Despite three copies, the skip rule ensures each "length" of 2s appears only once.
• No duplicates: nums = [1, 2, 3]. Should return all 8 subsets. The skip guard never triggers, and this reduces to the standard Subsets problem.
• Single element: nums = [5]. Should return [[], [5]]. No duplicates to skip.
• Empty array: nums = []. Should return [[]]. The empty set is always a valid subset.
• Two identical elements: nums = [1, 1]. Should return [[], [1], [1,1]]. The second 1 is skipped at the root level but included at a deeper level.

From understanding to recall

You understand the recursion tree. You see how sorting groups duplicates together and how i > start with the equality check skips same-level duplicates while still allowing identical values at different levels. But can you write the solution from scratch in under two minutes?

That is what interviews demand. The duplicate-skipping guard is easy to get wrong under pressure. Using i > 0 instead of i > start, forgetting to sort, or recording only at leaf nodes instead of at every node are all common mistakes that produce wrong answers. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the sorted-backtracking template and the same-level duplicate-skipping guard from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "subsets with duplicates" and the code flows out without hesitation.

The sorted backtracking and same-level duplicate skipping patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Subsets - The version with all unique elements. Compare the two to see how sorting and the duplicate-skipping guard are the only additions.
• Combination Sum II - Uses the same duplicate-skipping technique, but adds a target-sum constraint and early pruning when a candidate exceeds the remaining target.

CodeBricks breaks Subsets II into its sorted-backtracking and duplicate-skipping building blocks, then drills them independently with spaced repetition. You type the backtracking skeleton and the deduplication guard from scratch until they are automatic. When a backtracking-with-duplicates problem shows up in your interview, you do not think about it. You just write it.