Subsets II

The duplicate bug comes from treating equal input positions as different decisions. Sort first, then skip equal candidates only when they are siblings at the same recursion depth.

Read the contract and spot the duplicate-choice signal

You must return:

• Every value-based subset, including [].
• No duplicate subsets, even when the input contains repeated values.
• Any output order.

For nums = [1, 2, 2], selecting the first 2 and selecting the second 2 are different index choices, but they produce the same value-based subset [2]. The output contract cares about values, not which physical copy of 2 you selected.

There is a second distinction that matters:

• Selecting one 2 and selecting two 2s are different subsets.
• Selecting the first 2 or the second 2 as the only 2 produces the same subset.

That is the entire problem in miniature. We need to remove equivalent choices without removing valid multiplicities.

The backtracking structure is the same basic shape as ordinary subset generation:

1. Maintain the current subset.
2. Choose later elements only, so each input position is used at most once.
3. Record every current path because every path is a valid subset.
4. Avoid branches that differ only by swapping equal sibling values.

The standard Subsets II solution is therefore:

1. Sort nums.
2. Backtrack with a start index.
3. In each loop, skip nums[i] when it equals the previous value and i is not the first candidate at this recursion level.

The last condition is the part worth understanding. Memorizing it without understanding it is how this problem returns to haunt you.

Why ordinary power-set recursion duplicates output

A basic include/exclude recursion gives every input position its own decision. For three positions, it explores all eight index selections.

That is correct when values are distinct. With [1, 2, 2], it also explores choices such as:

• Select the first 2, not the second: [2]
• Do not select the first 2, select the second: [2]

Those are different index paths but the same output subset.

The same collision appears with [1, 2]:

• Select 1 and the first 2: [1, 2]
• Select 1 and the second 2: [1, 2]

A set-based cleanup after generation can remove repeated lists, but it leaves the search tree bloated and adds another representation problem. In Python, lists are mutable and unhashable, so you would need to convert subsets to tuples or use another deduplication structure.

That approach treats the symptom after the search has already done redundant work. The better fix is structural: prevent equivalent sibling branches from being created.

Sort and define the backtracking state

Sorting turns duplicate detection into a local comparison:

[1, 2, 2]

Equal values are now adjacent. The recursion can compare nums[i] with nums[i - 1] instead of searching for duplicates globally.

Use three pieces of state:

• path: the subset currently being built.
• start: the first index eligible for the next selection.
• result: copied snapshots of every valid path.

At a call backtrack(start), try every index i from start onward:

1. Append nums[i] to path.
2. Recurse with i + 1.
3. Pop the value to restore the parent state.

The transition to i + 1 matters. It means the same input position cannot be selected again, and later choices preserve a single left-to-right construction order.

Every call records path, including the root call where path is empty. There is no need to wait until start == len(nums). A partial path is already a complete subset.

State invariant: At backtrack(start), path is a valid subset formed from indices before start, and every legal continuation begins at an index at least start.

Sorting and increasing indices serve different jobs:

• Sorting exposes equal values beside one another.
• Increasing indices prevents position reuse and gives each subset a canonical construction order.

Do not confuse those responsibilities. Sorting alone does not deduplicate the search. The recursion rule does not detect equal values unless sorting has grouped them.

Skip duplicate siblings, keep deeper duplicates

The central guard is:

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

Read it literally:

At this recursion level, if this candidate equals a previous candidate, skip it.

The comparison is local to the current call. That is why the condition uses i > start, not i > 0.

Consider the root call for [1, 2, 2]:

path = []
start = 0

The loop sees:

i	Candidate	Action
0	1	Choose it
1	2	Choose the first 2
2	2	Skip: equal sibling at this level

Choosing index 1 for the root-level 2 is enough to represent the branch beginning with one 2. Choosing index 2 instead would expose the same value choices beneath it.

But after choosing the first 2, the recursive call starts at index 2:

path = [2]
start = 2

Now index 2 is the first candidate at this new level. The condition i > start is false, so the second 2 is allowed:

[2] -> [2, 2]

This is the distinction:

• Same level: equal candidates are interchangeable, so skip later siblings.
• Deeper level: another equal value may increase the subset's multiplicity, so keep it.

If you skip every repeated value globally, you lose [2, 2]. If you never skip repeated values, you emit duplicate [2] and [1, 2] branches.

Think of the first equal value as opening the doorway. Deeper recursion decides how many copies pass through it.

A compact trace

For the root path []:

i = 1, nums[i] = 2
  choose 2
  recurse from start = 2

    i = 2, nums[i] = 2
      choose 2
      emit [2, 2]
      undo

i = 2, nums[i] = 2
  skip: i > start and nums[i] == nums[i - 1]

The first 2 owns the root-level branch. The second 2 remains available underneath that branch.

That is what “skip duplicate branches” actually means. It does not mean “remove duplicate values from the input.” It means “remove duplicate sibling decisions.”

Prove coverage, uniqueness, and restoration

A few examples show the rule working. An invariant explains why it keeps working.

Coverage

Take any valid unique subset and write its values in the sorted traversal order. The algorithm can build it from left to right.

When the subset needs one copy of a repeated value, the first eligible occurrence is allowed at that recursion level. When it needs another copy, recursion moves deeper and the next occurrence becomes eligible there. Therefore, valid multiplicities remain reachable.

For [1, 2, 2], this preserves all of these:

[]
[1]
[2]
[1, 2]
[2, 2]
[1, 2, 2]

The algorithm skips only a later equal candidate competing for the same parent path. It does not skip the deeper choice needed to select another occurrence.

Uniqueness

Suppose two search paths produce the same value-based subset.

If they differ by choosing different equal values at the same recursion depth, the path using the later equal sibling is skipped. That collision cannot appear in the result.

If they differ in how many copies of a value they select, then they differ at a deeper recursion level. Those are genuinely different subsets, so both should remain.

If they differ by another value, their output values differ as well.

Thus, each unique subset has one surviving construction path.

State restoration

Backtracking reuses one mutable path. After exploring a choice, remove it before trying the next sibling:

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

Without the pop(), values leak from one branch into the next. Without copying when recording, every result entry may refer to the same list object and change as recursion continues.

Correctness has two moving parts: the duplicate guard controls which branches exist, while append/pop controls whether each branch starts from the correct parent state.

The sorted traversal may produce subsets in a predictable order, but the contract does not require any particular output ordering.

The Python Subsets II solution

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

        result = []
        path = []

        def backtrack(start: int) -> None:
            # Every path is a valid subset.
            result.append(path.copy())

            for i in range(start, len(nums)):
                # Skip equal siblings, but allow the first equal value
                # at each deeper recursion level.
                if i > start and nums[i] == nums[i - 1]:
                    continue

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

        backtrack(0)
        return result

The implementation has a short list of obligations:

• nums.sort() groups equal values.
• result.append(path.copy()) snapshots the current subset.
• i > start makes duplicate skipping level-local.
• backtrack(i + 1) prevents reusing the same input position.
• path.pop() restores the state before the next sibling.

Dry-run on [1, 2, 2]

After sorting, the search emits these paths:

[]
[1]
[1, 2]
[1, 2, 2]
[2]
[2, 2]

The root-level second 2 is skipped, so there is no second copy of [2] or [1, 2]. The deeper call beneath [2] still accepts the second 2, so [2, 2] remains.

The result order is not the important part. The important part is that each value-based subset appears once.

A useful interview debugging checklist:

1. Did you sort before recursion?
2. Is the guard exactly i > start, rather than i > 0?
3. Do you recurse with i + 1?
4. Do you copy path when storing it?
5. Does every append have a matching pop?

If one of those answers is wrong, the output usually tells you which assumption broke.

Complexity, edge cases, and failure checks

Let n be the input length, and let k be the number of unique subsets returned.

Sorting costs:

O(n log n)

The search generates subsets and copies each emitted path into result. Copying a subset of length d costs O(d), so the output itself requires work proportional to the total number of values stored across all returned subsets.

A safe worst-case bound is:

O(n log n + n · 2^n)

When all values are distinct, there are 2^n subsets, and the total amount of copied output can reach O(n · 2^n). With repeated values, duplicate skipping reduces the number of generated branches and returned subsets, but the worst-case bound remains the distinct-value case.

Space has two parts:

• Auxiliary search space: O(n) for recursion depth and the mutable path.
• Returned output: proportional to the number and lengths of the k subsets, up to O(nk).

Do not report only O(n) space if the function materializes every subset. That ignores the largest object the algorithm is building: the answer itself.

Edge cases worth testing

All values equal

nums = [2, 2, 2]

Expected value-based subsets:

[]
[2]
[2, 2]
[2, 2, 2]

This catches the mistake of skipping repeated values at every depth. The algorithm must preserve one-copy, two-copy, and three-copy choices.

All values distinct

nums = [1, 2, 3]

No duplicate guard fires, so the method behaves like ordinary subset generation and returns eight subsets.

Mixed negative and repeated values

nums = [-1, 0, 0, 2]

Sorting handles both comparison and grouping:

[-1, 0, 0, 2]

The values' signs do not change the backtracking logic.

Single element

For [5], the result must contain:

[]
[5]

Empty input, if allowed by a caller

The same structure naturally returns [[]]: the root path is the empty subset. The stated problem constraints require at least one input element, but this behavior is a useful structural check.

Common incorrect implementations

• Failing to sort: equal values may not be adjacent, so the local comparison cannot reliably identify duplicate siblings.
• Using i > 0: this skips equal values even when they are the first candidate in a deeper call, removing valid subsets such as [2, 2].
• Skipping repeated values globally: duplicate values are not interchangeable across depths. Their count matters.
• Recursing with i instead of i + 1: the same input position can be selected repeatedly.
• Appending path directly: later mutations change previously stored results.
• Deduplicating only after generation: it may produce correct values, but it searches redundant branches and obscures the actual structure of the solution.

The transferable pattern

When repeated candidates can create the same output, ask one precise question:

Are these equal choices competing as siblings, or is a deeper choice needed to increase multiplicity?

If they are siblings, sort the candidates and skip later equal values at that recursion depth. If a deeper selection can produce a genuinely different result, preserve it.

For Subsets II, the implementation check is compact:

sort
compare only when i > start
recurse from i + 1
copy the path
pop after recursion

That is the reusable move: deduplicate equivalent sibling branches without pruning valid deeper states. Once you can see that boundary, many combination-style backtracking problems stop looking like a pile of special cases and start looking like the same search tree with a carefully placed gate.