L31 · Backtracking I — Subsets & Combinations

Series: LeetCode — From Basics to Interview-Ready · Session 31 / 65 · Phase 1 · Core patterns

Why this session exists

Subsets, combinations and permutations look like three problems. They are one problem with three different loop bounds. If you learn them separately you carry three templates and mix them up under pressure. If you learn the shared skeleton you carry one, and the differences reduce to a single parameter you can reason about at the whiteboard.

The skeleton is three lines and it never changes: append the choice, recurse, pop the choice. Everything interesting lives in the loop that decides which choices are available at this depth. Subsets and combinations pass a start index so each element can only be chosen after the ones before it, which kills reorderings. Permutations pass a used array instead, because reorderings are exactly what you want.

The other reason for this session is the duplicate-handling rule, which is genuinely subtle and comes up constantly. Sort, then skip an element if it equals its predecessor and its predecessor is not currently in the path. That sentence is worth reading three times.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

path.append(x)
bt(...)
path.pop()

Concretely: write subsets(nums) returning all 2^n subsets, using the recursive form with a start index. Then, without looking at it, write permute(nums) returning all n! permutations.

What wobbles: appending path itself instead of path[:] to the results (every entry ends up as the same, eventually empty, list), and forgetting the pop (the path only grows and every result is wrong).

Pattern anatomy

The shape of problem that summons backtracking: enumerate all objects satisfying a structural constraint, where each object is built by a sequence of independent choices. The output is a list of things, not a number. If the problem wants a count, or a maximum, and the search space is exponential, you are probably looking at DP instead — that is sessions 33 onward.

The invariant: path always holds a valid partial object for the current recursion depth, and by the time a call returns, path is byte-for-byte what it was when the call was entered. That restoration property is what "backtracking" names, and it is why the pop is mandatory rather than tidy.

The skeleton:

def backtrack(path, choices):
    if is_complete(path):
        results.append(path[:])       # COPY: path keeps mutating
        return
    for c in choices:
        if not is_valid(c, path):
            continue
        path.append(c)                # choose
        backtrack(path, next_choices(c))
        path.pop()                    # un-choose

Subsets — every node in the recursion tree is an answer, not just the leaves:

def subsets(nums):
    res, path = [], []
    def bt(start):
        res.append(path[:])           # record at EVERY node
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)                 # i+1: never reuse, never reorder
            path.pop()
    bt(0)
    return res

Combination Sum — reuse allowed, so recurse on i rather than i + 1:

def combinationSum(candidates, target):
    candidates.sort()
    res, path = [], []
    def bt(start, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break                 # sorted, so everything after is worse
            path.append(candidates[i])
            bt(i, remain - candidates[i])   # i, not i+1: reuse allowed
            path.pop()
    bt(0, target)
    return res

Permutations — order matters, so there is no start; you track what is already used:

def permute(nums):
    res, path = [], []
    used = [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False           # restore BOTH pieces of state
    bt()
    return res

Subsets II — duplicates in the input, and each distinct subset must appear once:

def subsetsWithDup(nums):
    nums.sort()                       # equal values must be adjacent
    res, path = [], []
    def bt(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue              # skip a duplicate at the SAME depth
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res

if i > start and nums[i] == nums[i-1] is the line to understand rather than memorise. At a given recursion depth, choosing the first 2 and choosing the second 2 produce identical subtrees, so you take only the first. The i > start guard is what limits the skip to this depth — the second 2 is still allowed when it is being chosen at the next depth down, which is how [2, 2] still gets generated.

The cue

You are looking at a backtracking problem when the statement contains one of these tells:

1. "Return all", "find all", "list every". The output is a collection of solutions, not a single value. This is the strongest tell in the whole series.
2. Tiny constraints. n <= 20 for subsets, n <= 8 for permutations, n <= 9 for grids. Exponential output demands a small n, so a suspiciously small bound is a direct hint that exponential enumeration is intended.
3. "All combinations / permutations / partitions / arrangements". Literal vocabulary.
4. Building a string or sequence choice by choice — Letter Combinations of a Phone Number, Generate Parentheses, Palindrome Partitioning.
5. A constraint that can be checked incrementally. If you can tell that a partial object is already doomed, backtracking with pruning is the right frame. That is session 32.

The negative cue is important. "How many" instead of "list all" usually means DP or combinatorics, not enumeration — you should not generate 2^40 objects to count them. And if n is large with an exponential-looking question, the intended answer is almost certainly polynomial and you are misreading the problem.

Guided solve

Subsets. Given an array of distinct integers, return all possible subsets, in any order.

Start by counting the output. Each of n elements is independently in or out, so there are exactly 2^n subsets. That number is worth stating: it establishes that no algorithm can beat O(2^n) here, because merely writing the answer costs that much. Saying this up front reframes the question from "can you make it fast" to "can you enumerate cleanly", which is what is actually being tested.

Two mental models produce two implementations, and both are worth knowing.

Model one: include-or-exclude. At index i you either take nums[i] or you do not, then move to i + 1. A binary tree of depth n, and the leaves are the answers.

def subsets_binary(nums):
    res, path = [], []
    n = len(nums)
    def bt(i):
        if i == n:
            res.append(path[:])
            return
        bt(i + 1)                     # exclude nums[i]
        path.append(nums[i])          # include nums[i]
        bt(i + 1)
        path.pop()
    bt(0)
    return res

Model two: the start-index loop, which is the version I write in interviews:

def subsets(nums):
    res, path = [], []
    def bt(start):
        res.append(path[:])           # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res

The second is better because it generalises. Change res.append(path[:]) to a length check and you have Combinations. Change bt(i + 1) to bt(i) and you have Combination Sum with reuse. Add the duplicate skip and you have Subsets II. One shape, four problems. The binary form does not extend nearly as gracefully.

Why path[:] and not path? Because path is a single list object mutated throughout the entire recursion. Appending the reference stores a pointer, and when the recursion finishes, every stored pointer refers to the same now-empty list. The output is [[], [], [], ...]. This bug is universal on first attempt, and it is worth writing path[:] deliberately rather than reflexively so you can explain it.

Trace on [1, 2]. bt(0) records []. Loop i=0: path [1], bt(1) records [1]; loop i=1: path [1,2], bt(2) records [1,2], pop to [1]; return, pop to []. Loop i=1: path [2], bt(2) records [2], pop. Result: [], [1], [1,2], [2]. Four subsets, which is 2^2. Correct.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• Combination Sum — candidates may be reused unlimited times. Decide before you code whether the recursive call passes i or i + 1, and be able to say why in one sentence.
• Permutations — no start index here. Think about what state has to be restored on the way out: it is two things, not one.
• Subsets II — the input has duplicates. Sort first, then work out the exact condition under which you skip an element. Write the condition on paper before coding it.

If all three land early, do Palindrome Partitioning. Same start-index skeleton, with an is_palindrome check as the validity filter.

Common failure modes

Appending path instead of path[:]. Every result ends up as a reference to one mutating list, so the final output is all empty lists. Universal on first attempt.

Missing the pop. The path only ever grows, so depth-2 results contain depth-1 leftovers. The first few outputs look right, which delays the diagnosis.

Restoring only half the state in permutations. You must undo both path.append and used[i] = True. Forgetting the used reset silently drops most permutations, and the output is short rather than wrong-looking.

Using i + 1 when reuse is allowed, or i when it is not. bt(i) permits reusing the current element; bt(i + 1) forbids it. Getting this backwards in Combination Sum gives either too few results or infinite recursion.

Skipping duplicates with i > 0 instead of i > start. The i > 0 form skips the second 2 at every depth, so [2, 2] never gets generated. The i > start form only skips it as a sibling at the same depth, which is exactly what you want.

Forgetting to sort before duplicate handling. The skip condition compares adjacent elements, so equal values must be adjacent. Without the sort the condition never fires and duplicates flood the output.

Complexity

Subsets: O(n · 2^n) time. There are 2^n subsets, and copying each one into the result costs O(n) in the worst case. The recursion itself visits exactly 2^n nodes. You cannot do better, because the output alone has that many elements.

Permutations: O(n · n!) time. There are n! permutations and each costs O(n) to copy. Note that a naive used scan adds a factor of n inside each level, but since the copy already costs n, the bound is unchanged.

Combination Sum: O(n^(target/min)) in the worst case — the recursion depth is bounded by target / min(candidates) because each choice subtracts at least the minimum candidate, and each level branches up to n ways. This is a loose bound; the sorted break prune cuts it substantially in practice, though not asymptotically.

Space: O(n) auxiliary, excluding the output. The recursion stack is at most n frames deep for subsets and permutations, and the shared path buffer holds at most n elements. The output itself is O(n · 2^n) or O(n · n!) but that is required, not overhead — always state the distinction, because "exponential space" sounds alarming until you point out that the answer is exponential.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Subsets enters the queue today. Subsets II should go in at a shorter interval than you think it deserves — the duplicate-skip condition is the single most forgotten line in this session, and re-deriving it from scratch each time is exactly the skill you want.