Subsets II

Subsets II takes the classic "list every subset" problem and adds a twist: the input can contain duplicates, and you must not return the same subset twice. It is the canonical lesson in how to prune duplicate branches during backtracking.

The slow way first

The obvious idea: generate every subset with plain backtracking (at each index, choose take-or-skip), collect them, then throw the duplicates away at the end — usually by sorting each subset and stuffing them into a set.

That works, but it does real wasted work: with many repeated values you generate an exponential number of subsets only to discard most of them, and the dedup set costs extra memory. The better move is to never create the duplicate in the first place.

The idea: sort, then skip a repeat at the same depth

First sort nums, so equal numbers sit next to each other. Then backtrack normally, but inside each call's loop add one rule: at the same tree depth, only branch on the first occurrence of a value. Concretely, the loop runs i from start; if i > start and nums[i] == nums[i-1], we continue — that value was already tried at this depth, so taking it again would rebuild an identical subtree.

The subtle part is i > start. We only skip when the repeat appears later in the same loop. The very first time a value shows up at this depth (i == start) we must still take it — that branch is legitimate.

Walk through it

Step through the animation on nums = [1, 2, 2]. Each node is one recursive call, labelled with the subset built so far; every node we reach is recorded. Watch the two dimmed branches: a second 2 at the root and a second 2 under [1]. In both, i > start and nums[i] == nums[i-1], so the dedup line skips them — preventing a duplicate [2] and [1,2] subtree.

Pseudocode

sort nums
res = []
backtrack(start, path):
    record a copy of path                 # every path is a valid subset
    for i from start to end of nums:
        if i > start and nums[i] == nums[i-1]:
            skip this i                    # duplicate at this depth
        add nums[i] to path
        backtrack(i + 1, path)
        remove nums[i] from path           # undo for the next choice
backtrack(0, empty path)
return res

The Python solution

def subsets_with_dup(nums):
    res = []
    nums.sort()
    def backtrack(start, path):
        res.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 res

• nums.sort() groups equal values so duplicates are adjacent — the dedup test depends on this.
• res.append(path[:]) records a copy of the current path; every node in the tree is a valid subset.
• The loop runs i from start, so each recursion only considers indices to the right (subsets, not permutations).
• Line 7 is the heart of it: i > start and nums[i] == nums[i-1] skips a value already tried at this depth, killing the duplicate branch.
• path.append / backtrack(i + 1, ...) / path.pop() is the take-recurse-undo rhythm of backtracking.

Complexity

There are up to 2^n subsets and copying each costs O(n), giving O(n · 2^n) — unavoidable since that is the output size. The sort is O(n log n), dwarfed by the rest. Extra space is O(n) for the recursion depth and the current path (excluding the output).

When this pattern shows up

Practice