Backtracking

Backtracking is DFS over a space of decisions rather than over a data structure. There is no graph in the input; the tree is the set of partial answers you could build, and you walk it by making one choice at a time.

The template barely changes between problems — choose, explore, un-choose — which is why these problems look interchangeable once you have written two of them. What actually varies is narrower than it looks: how you avoid generating the same thing twice, and where you cut a branch off early.

The tree you are walking#

Every node is a partial candidate. Its children are the ways of extending it by one more choice. The recursion walks that tree depth-first, and the path from the root to wherever you currently are is the candidate under construction.

Two things to notice. Every node here is an answer, not just the leaves — a subset is valid at any size, which is why the result is recorded on arrival. And watch the path row between steps: moving sideways in the tree always means undoing choices before making new ones. That undo is the entire technique, and the reason the whole walk needs only one array rather than a fresh copy per branch.

path = empty
results = empty

function backtrack(start):
    record a COPY of path                 // for subsets: every node counts

    for i = start .. n - 1:
        path.append(nums[i])              // CHOOSE
        backtrack(i + 1)                  // EXPLORE, from after i
        path.remove_last()                // UN-CHOOSE

The interactive subsets snippet builds exactly this in Go, line by line, and is worth stepping through once — every other problem on this page is that function with a different record, a different loop bound, or an extra check inside the loop.

Record a copy#

path is one array that the whole recursion shares and keeps mutating. Appending it to the results without copying stores a reference, and by the time the walk finishes, every entry in your results list is the same — empty — array.

This is the most common backtracking bug, it produces output that is the right length and entirely wrong, and it does not exist in languages where the natural move builds a new string or list anyway.

Three shapes#

Almost every problem is one of these, and the difference between them is one line.

Subsets — order does not matter, so [1,2] and [2,1] are the same answer. Pass a start index and loop from it, which makes each element only ever considered after everything before it. That single constraint is what stops permutations of the same set from appearing.

Combinations — subsets with a target: a fixed size k, or a required sum. Same start index, but the recording moves from “always” to “only when the target is met”, and you get to stop early when it cannot be.

Permutations — order does matter, so every element must be reachable at every position. There is no start index; the loop runs over all n every time, and a used array keeps you from picking the same element twice on one path.

function permute():
    if len(path) == n:
        record a copy of path
        return

    for i = 0 .. n - 1:
        if used[i]:  continue        // already on this path

        used[i] = true;  path.append(nums[i])
        permute()
        used[i] = false; path.remove_last()    // un-choose BOTH

Note that the undo has two halves now. Anything you changed on the way in has to be restored on the way out — miss one and the corruption shows up several branches later, which is miserable to debug.

Combination Sum adds a third variation: elements may be reused. That is one character — recurse on i rather than i + 1, so the same index is available again at the next level. The recursion still terminates, because the target strictly decreases.

Pruning is the point#

Backtracking is exponential and always will be. Pruning is what decides whether it finishes.

The idea is to abandon a branch the moment it cannot lead to an answer, rather than discovering that at the bottom. For Combination Sum, sort the candidates first and stop the loop — not just skip the iteration — as soon as one exceeds the remaining target:

sort(candidates)

function backtrack(start, remaining):
    if remaining == 0:  record a copy of path;  return

    for i = start .. n - 1:
        if candidates[i] > remaining:
            break                    // sorted, so everything after is worse too

        path.append(candidates[i])
        backtrack(i, remaining - candidates[i])   // i, not i+1: reuse allowed
        path.remove_last()

break rather than continue is the whole payoff of having sorted. It is also the difference between a solution that passes and one that times out on the larger cases.

The general form of the question is worth remembering, because it transfers to problems that look nothing like this one: given what I have chosen so far, is any completion still possible? If you can answer that cheaply, you have a prune.

Duplicates in the input#

When the input itself contains repeats, the same candidate gets generated by different routes and the output has duplicates. The fix is standard and worth memorising: sort the input, then skip a value that equals its predecessor unless the predecessor was chosen at this level.

sort(nums)

for i = start .. n - 1:
    if i > start and nums[i] == nums[i - 1]:
        continue                     // this value already led a branch here
    ...

The condition i > start is doing precise work. At each level, the first occurrence of a value is allowed to start a branch; later occurrences at the same level would produce an identical subtree, so they are skipped. Occurrences deeper down are fine, because there the value is being added to a path rather than replacing an equal sibling. Sorting is what puts the equal values next to each other so the test is a single comparison.

Backtracking on a grid#

Word Search looks like a different problem and is the same one. The choices are the four directions, the path is the cells visited so far, and the mark-and-unmark is what keeps a path from crossing itself:

function search(r, c, k):
    if k == len(word):  return true
    if out of bounds or grid[r][c] != word[k]:  return false

    grid[r][c] = VISITED                 // choose: claim this cell
    for (dr, dc) in DIRS:
        if search(r + dr, c + dc, k + 1):  return true
    grid[r][c] = word[k]                 // un-choose: release it

    return false

The difference from an ordinary DFS flood is exactly the last line. A flood fill marks cells permanently, because it wants each cell once. Here the mark is scoped to the current path — a cell that failed on this route must still be available to a different one, so releasing it is mandatory. Forgetting to restore it makes the first failed attempt poison every attempt after it.

When you do not need to undo#

If instead of mutating one shared path you pass a fresh value down — a new string, a new list — there is nothing to un-choose, because the caller’s copy was never touched:

function backtrack(index, prefix):
    if index == len(digits):
        record prefix;  return

    for ch in letters[digits[index]]:
        backtrack(index + 1, prefix + ch)      // a new string each time

Letter Combinations of a Phone Number is usually written this way, and it is genuinely simpler. The cost is a fresh allocation per node instead of one array reused throughout, which for short outputs is irrelevant and for large ones is not. Know both; pick the mutating version when the path is long, and say why.

Talking about the cost#

Interviewers ask, and the answer has a shape:

• Subsets — O(n · 2ⁿ). There are 2ⁿ subsets and copying each one costs up to n.
• Permutations — O(n · n!), by the same argument.
• Combination Sum — exponential in target ÷ smallest candidate; there is no tidy closed form, and saying so plainly is better than inventing one.

The pattern is number of nodes in the tree × the work at each node, and the work at each node is usually the copy. Pruning does not change the worst case, which is worth being upfront about — it changes the cases you actually get.

Recognising it#

Reach for backtracking when:

• The problem asks for all of something — all subsets, all permutations, all valid arrangements — rather than a count or a best one. If it asks only for the count or the optimum, check whether dynamic programming applies first; it usually does, and it is usually much faster.
• You are building a candidate incrementally, and partial candidates can be judged before they are complete.
• The input is small — n around 20 or less, or a board of modest size. Exponential is acceptable only because n is tiny, and a small bound in the constraints is a strong hint.
• The phrase “all possible” appears anywhere in the statement.

Then, before writing: decide whether order matters (start index or used array), whether elements repeat (sort and skip), and what makes a branch hopeless (the prune).

Summary#

Choose, explore, un-choose — and the third one is where the bugs live. Whatever you changed on the way in gets restored on the way out, including marks that are not part of the path itself. Record copies, never references. Beyond that the technique is a small set of variations: start for combinations and used for permutations, sorting to make both pruning and duplicate-skipping into single comparisons, and the honest admission that the whole thing is exponential — pruning just decides whether that matters here.