Backtracking I — Subsets & Combinations

Review boundary and corrected contracts

Enumeration complexity includes copying output: Θ(n·2ⁿ) for all subsets and Θ(n·n!) for all permutations of distinct items. Positive distinct candidates make Combination Sum finite. Sorting changes the caller list; duplicate skipping applies at the same recursion depth.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for greedy & backtracking is in the 6-month plan: S034 — theory.

Learning objective: Learn one backtracking template — choose, explore, un-choose — and derive subsets, combinations and permutations from it without memorising three separate algorithms.

Series: LeetCode — From Basics to Production-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.

Duplicate handling depends on the traversal. For subsets, sort and skip equal siblings with i > start. For permutations with duplicate values, skip i when i > 0 and nums[i] == nums[i-1] and not used[i-1]: this chooses equal copies in index order while still allowing both copies in one permutation. The plain permute below assumes distinct input values.

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 is pseudocode: is_complete, is_valid, next_choices and results are supplied by the problem. The complete functions below specialize it.

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 — positive, distinct integer candidates and a non-negative integer target; reuse is allowed, so recurse on i rather than i + 1. Zero would make remaining-target recursion fail to progress, negatives remove the depth bound, and duplicate candidates would duplicate outputs. sort() intentionally mutates the caller’s list:

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 an Ω(2^n) lower bound just to identify all results, and Ω(n·2^n) to materialize their elements in lists. 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 practice:

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. Record and return when len(path) == k to get fixed-size Combinations; stop branches too short to reach k. For Combination Sum, changing i+1 to i only enables reuse: also carry a remaining target, record only at zero, and prune oversized positive candidates. 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.

Bit-mask enumeration iterates masks from 0 to 2^n−1 and includes nums[i] when bit i is set. It avoids recursion, but is not inherently faster than the start-index walk; scanning all n bits per mask also costs Θ(n·2^n). There is no correctness limit at n=20: output size and memory set the practical limit. Masks can filter subset sums or canonicalize duplicate-valued subsets, though they do not by themselves encode arbitrary permutations or unbounded reuse.

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 the wrong next index. In Combination Sum with positive candidates, bt(i+1) incorrectly forbids reuse and drops answers such as [2,2] for target 4. The displayed bt(i, remain-candidates[i]) terminates because remain decreases. In the plain subsets function, changing bt(i+1) to bt(i) causes unbounded reuse with no target to stop it, so Python eventually raises RecursionError.

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 sorting, separated equal values are not skipped; some adjacent duplicates may still be skipped, but uniqueness is no longer guaranteed.

Myth: Subsets, combinations and permutations need three different algorithms, so I have to memorise three templates.

Why: They share one skeleton — choose, explore, un-choose — and differ only in which choices are legal at each depth. Subsets and combinations pass a start index, which forbids reordering and makes {1,2} and {2,1} the same object. Permutations pass a used array instead, precisely because reordering produces distinct objects. Combination Sum recurses on i instead of i+1 to permit reuse. Three parameters, one template. Memorising three separate algorithms means you will reach for the wrong one when the problem is phrased unfamiliarly.

Steps 1: Because each element of the answer is built from a sequence of independent choices, the full solution space is a tree whose depth is the number of choices.

Steps 2: Because a depth-first walk of that tree reaches every node exactly once, it enumerates every candidate exactly once.

Steps 3: Because the walk shares one mutable path buffer instead of copying at every level, the extra space is O(depth) rather than O(number of solutions × depth).

Steps 4: Because sharing the buffer requires it to be identical on entry and exit of each call, the un-choose step is a correctness requirement, not a cleanup nicety.

Steps 5: Because the recorded results must survive later mutation of that buffer, each recorded result must be a copy.

Steps 6: Therefore for n distinct elements the start-index subsets walk visits exactly 2^n nodes — and the testable prediction is that instrumenting the recursion with a counter on an input of size 10 yields exactly 1024 recorded results and 1024 function entries, with the buffer length back at zero when the outer call returns.

Picture: You are walking a maze holding a piece of chalk. At every junction you mark the branch you take, walk it to the end, then walk back and rub the mark out before trying the next branch. The chalk trail is always exactly the route you are currently on — never a route you already finished.

Trigger: Fires on 'return all' or 'find every' with a small n, where each answer is assembled from a sequence of independent choices.

Name: Recursive backtracking with a shared path

Gain: O(depth) extra space; one template covers subsets, combinations, permutations and partitions; pruning drops in naturally

Cost: Requires disciplined state restoration — every mutation on the way in needs an exact undo on the way out

Name: Iterative build-up (start with [[]], extend with each element)

Gain: No recursion, no undo discipline, very short for subsets specifically

Cost: Materializes output as it grows; copies each prior subset when extending it with the new element. It can be adapted to constraints, but the recursive form exposes pruning state more directly

Name: Bit-mask enumeration

Gain: Simple subset representation with no recursion stack; speed depends on implementation and workload

Cost: Still enumerates 2^n index subsets; n≈20 is a practical size hint, not a correctness boundary. Targets and duplicates require additional filtering or canonicalization

Pick: Recursive backtracking whenever the problem may grow a constraint, a target, a duplicate rule, or a pruning opportunity — which is every design review variant beyond plain Subsets. Bit-mask only when the problem is literally 'enumerate all subsets of an array with n at most 20' and nothing more.

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: let D=floor(target/min(candidates)), for a nonempty list of n positive distinct candidates. Depth is at most D, not n. A safe loose bound including loop tests and copying is O(n log n + (n+D)·sum(n^d, d=0…D)); for n=1 the sum is D+1, so the cost does not misleadingly become constant. A more useful accounting is O(n log n + examined candidate choices + total output elements). The sorted break avoids checking the rest of an oversized suffix; it can greatly reduce work on an input, but the search still has combinatorial worst-case output.

Space: subsets and permutations use O(n) auxiliary stack/path/flags, excluding their materialized output. Combination Sum instead uses O(D) stack/path plus up to O(n) temporary sorting space in CPython: O(n+D) auxiliary space. Its output stores the sum of lengths of accepted combinations. The empty candidate list returns [[]] for target 0 and [] for a positive target; D is undefined there. Recursion depth limits still apply even if the output is small.

For subsets of n≥1 distinct values, each value occurs in exactly 2^(n−1) results, so the total copied elements are n·2^(n−1), proving Θ(n·2^n) time and output storage. The start-index traversal has 2^n calls; the binary include/exclude version has 2^(n+1)−1 calls but the same 2^n answers.

Self-check (answer follows each question).

Q: Why must you append path[:] rather than path to the results list?

A: path is one mutable list shared across the entire recursion. Appending the reference stores a pointer that keeps changing, so after the recursion completes every stored entry points at the same empty list.

Q: Which index change enables reuse, and what else is needed to turn Subsets into Combination Sum?

A: Passing i instead of i+1 lets the current candidate be chosen again. Also track the remaining target, record only when it reaches zero, and stop oversized positive candidates. Changing the index alone in plain Subsets removes progress and does not implement Combination Sum.

Q: Why do permutations use a used array instead of a start index?

A: A start index forbids revisiting earlier elements, which eliminates reorderings — correct for combinations, fatal for permutations where reorderings are distinct answers. The used array allows any unused element at any depth while still preventing repeats within one permutation.

Q: In Subsets II, why is the duplicate skip condition i > start rather than i > 0?

A: The skip must apply only among siblings at the same recursion depth, where identical values generate identical subtrees. i > 0 would also skip the duplicate when it is legitimately being chosen at a deeper level, so [2, 2] would never be produced.

Q: What are the two pieces of state that must be restored on the way out of a permutation recursion?

A: The path — pop the appended element — and the used flag — set used[i] back to False. Restoring only one silently truncates the output.

Q: Combination Sum sorts the candidates and breaks out of the loop when candidates[i] > remain. Does this change the asymptotic complexity, and why does the sort make break valid instead of continue?

A: Sorting makes every later candidate at least as large, so once one exceeds remain, the whole suffix is impossible and break is sound. Without this ascending-order invariant use continue rather than discarding potentially smaller later candidates. Pruning changes the number of choices examined and can improve instance costs; it does not remove the worst-case cost of generating all accepted output.

Stretch: true

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.

• One skeleton: choose, explore, un-choose. Subsets, combinations and permutations differ only in which choices are legal at each depth.

• start index forbids reordering, so it gives combinations. used array permits reordering, so it gives permutations.

• bt(i) allows reuse of the current element; bt(i + 1) forbids it. That one character is the whole difference in Combination Sum.

• Always record path[:], never path. The buffer is shared and keeps mutating.

• Duplicates: sort first, then skip when i > start and nums[i] == nums[i-1]. The i > start limits the skip to siblings at one depth.

• Exponential output means exponential time is not a failure. State the output size up front — it reframes the question as clean enumeration rather than optimisation.

Corrective source notes

• CPython 3.14.0 list methods and sorting implementation notes — list.sort mutates its input and may need O(n) temporary pointers; read fresh 2026-10-09.
• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.