Backtracking

Backtracking is recursion over shared mutable state. The tree is the one from the recursion framework, but instead of every call building and returning its own answer, every call writes into one buffer, recurses, and then removes exactly what it wrote.

That last clause is the whole technique. Three lines, always in this order: choose, recurse, un-choose.

The skeleton

def subsets(a):
    out, path = [], []

    def go(i):
        if i == len(a):
            out.append(list(path))   # a copy — path keeps changing
            return
        path.append(a[i])            # choose a[i]
        go(i + 1)                    # recurse
        path.pop()                   # un-choose
        go(i + 1)                    # the branch that leaves a[i] out

    go(0)
    return out

The mission statement still has to be written, and for a mutating helper it reads: "appends to out one copy of every subset of a[i:], each prefixed by the current contents of path". Both accumulators are named in it, which is what tells you the copy is needed.

The subset decision tree for two items, and the pop that restores the parent state100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

What a forgotten un-choose produces

Delete the path.pop() and run it on [1, 2]. State now leaks sideways: the skip branch inherits whatever the take branch left behind. The four leaves record [1,2], [1,2], [1,2,2], [1,2,2] instead of [1,2], [1], [2], []. The count is right and every value is wrong, because path only ever grows.

The sibling bug is dropping the copy — out.append(path) instead of out.append(list(path)). Every recorded answer is then the same list object, so the output is four references to one buffer, and that buffer is empty by the time the recursion unwinds. You get [[], [], [], []]. Both bugs produce 2² = 4 entries, which is why a length check passes and the content is nonsense.

Three families

Subsets — include or exclude. One binary decision per element, depth n, 2ⁿ leaves. At n = 20 that is 2²⁰ ≈ 1.05 million leaves; at roughly 10⁸ simple operations per second the traversal is milliseconds, which is why a constraint of n ≤ 20 is a licence to enumerate. The copies dominate the real cost: a million subsets averaging 10 elements is about 10 million cells written, so the honest complexity is O(n·2ⁿ), not O(2ⁿ).

Arrangements — which element goes next. An n-way decision at every level with a used marker, depth n, n! leaves:

def permutations(a):
    out, path, used = [], [], [False] * len(a)

    def go():
        if len(path) == len(a):
            out.append(list(path))
            return
        for i, x in enumerate(a):
            if used[i]:
                continue
            used[i] = True           # choose: two pieces of state
            path.append(x)
            go()
            path.pop()               # un-choose: both of them
            used[i] = False

    go()
    return out

Two mutations before the call, two after it. The rule generalises: every write made on the way down needs its mirror on the way up, and the mirrors go in reverse order. Factorials grow past the enumerable fast — 8! = 40,320, 10! = 3,628,800, 12! ≈ 479 million — so n = 10 is about the practical ceiling without pruning.

Grid decisions — four directions with a visited marker. The cell itself is the shared state:

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def exists(grid, word):
    R, C = len(grid), len(grid[0])

    def go(r, c, k):
        if k == len(word):
            return True
        if not (0 <= r < R and 0 <= c < C) or grid[r][c] != word[k]:
            return False
        keep, grid[r][c] = grid[r][c], '#'    # choose: mark visited
        found = any(go(r + dr, c + dc, k + 1) for dr, dc in DIRS)
        grid[r][c] = keep                     # un-choose
        return found

    return any(go(r, c, 0) for r in range(R) for c in range(C))

Restoring the cell is exactly what separates path search from flood fill. Keep the mark and each cell is consumed once, so the whole grid is O(R·C) — that is connected components, a different and much cheaper problem. Restore it and a cell can be reused by a different path, which is the point and also the cost: a word of length 8 is 7 moves, the first with four directions open and every later one with three because the cell it came from is still marked, so a start cell bounds at 4 × 3⁶ = 2,916 paths and a 10 × 10 grid at about 291,600 in the worst case.

Duplicate input: sort, then skip the repeat at this level

Given [1, 2, 2], the raw tree still has 2³ = 8 leaves, but there are only (1 + 1) × (2 + 1) = 6 distinct subsets: two choices for the 1, three for how many 2s. The extra branches exist because the two 2s are interchangeable — one branch is a relabelling of another.

The fix, in the which-element-goes-next framing:

def subsets_with_dups(a):
    a = sorted(a)                 # equal values become adjacent
    out, path = [], []

    def go(start):
        out.append(list(path))
        for i in range(start, len(a)):
            if i > start and a[i] == a[i - 1]:
                continue          # this value was already tried at this level
            path.append(a[i])
            go(i + 1)
            path.pop()

    go(0)
    return out

The guard is i > start, never i > 0, and the difference is the whole rule. i > start forbids opening a second sibling branch at this level with a value already tried here. When i == start the equal value is being appended below the previous one rather than beside it, which is a genuinely different subset — that case is how [1, 2, 2] still gets produced. The eight leaves of the include/exclude tree become six recorded subsets, and the six are distinct.

Sorting first is what makes the test a single comparison with the left neighbour. Unsorted, equal values are scattered, and "have I used this value at this level" needs a set allocated per node. One O(n log n) sort buys an O(1) test at every one of the 2ⁿ nodes; the arithmetic on that trade is in complexity by counting.

In an interview

Narrate the three lines and name the state: "I mutate path and used, I recurse, and I undo both in reverse order." Then name the copy before you are asked — "list(path), not path, because path is one shared buffer" — because that is the line an interviewer is watching for.

For duplicates, say why sorting comes first. "Sorting makes equal values adjacent, so skipping a repeated value at the same level is a comparison with the previous index rather than a per-level set." That sentence is the whole answer, and it separates people who memorised the guard from people who can re-derive it.

The mistake that loses points: quoting the complexity as O(2ⁿ) when every leaf copies a list of average length n/2. The generation is O(2ⁿ); the output is O(n·2ⁿ), and for n = 20 that factor of 10 is the difference between the number you said and the work the machine does.

Check yourself

On [1, 2, 2], how many leaves does the unguarded tree have, how many distinct subsets exist, and when does the guard fire?

2³ = 8 leaves against 6 distinct subsets. The guard fires when the second 2 would start a branch beside the first 2 at the same level, and stays quiet when the second 2 extends the first one's branch, which is why [1, 2, 2] survives.

You delete used[i] = False from the permutation code but keep path.pop(). What does it return for [1, 2, 3]?

Exactly one permutation, [1, 2, 3]. Nothing is ever released, so after the first root-to-leaf descent every index is marked and every later branch finds no candidate to try.

A grid path search never restores the cell it marked. What problem is it solving now?

Reachability — flood fill, or connected components — in O(R·C) instead of a path search. A cell consumed by a dead-end branch is never returned, so it is answering "which cells can be reached" rather than "is there a path spelling this word".