Backtracking: Three Beats

Backtracking is one loop structure wearing many names. Whether the question says subsets, permutations, or combinations-that-sum, the skeleton never changes: choose an option, explore what follows from it, unchoose — take the option back so the next branch starts clean. What changes between the three classic problems is not the beats but two numbers: where the loop starts, and whether an option may repeat.

The skeleton, once

export function subsets(values: number[]): number[][] {
  const results: number[][] = []
  const path: number[] = []

  function backtrack(start: number): void {
    results.push([...path]) // every prefix is itself an answer
    for (let i = start; i < values.length; i++) {
      path.push(values[i] as number)
      backtrack(i + 1)
      path.pop()
    }
  }

  backtrack(0)
  return results
}

The line people delete by accident is the pop. Understand what it actually is: path is one array shared by every branch of the recursion tree. A branch that finishes with its choice still on the path poisons every branch that runs after it — subsets acquire repeated values, and results that were never chosen appear. The pop is not cleanup after the algorithm; the pop is the algorithm — it restores the exact precondition the next iteration of the loop depends on. Also notice results.push([...path]) — a copy, not the array itself, because the shared path keeps mutating after the push.

for (let i = start; i < values.length; i++) {
  path.push(values[i] as number)
  backtrack(i + 1)
  path.()
}

The start index is the deduplication machine

Permutations pass the whole list and track membership, because every arrangement reorders everything. Combinations pass a start index and never look back — and that single parameter is what makes [1, 2] and [2, 1] one answer instead of two. Each branch may only choose from positions at or after the previous choice, so every multiset is built in exactly one order.

For combinations with reuse — the coins problem — the recursive call stays at the same index instead of past it:

function backtrack(start: number, remaining: number): void {
  if (remaining === 0) {
    results.push([...path])
    return
  }
  for (let i = start; i < candidates.length; i++) {
    const value = candidates[i] as number
    if (value > remaining) continue
    path.push(value)
    backtrack(i, remaining - value) // same i: this coin may repeat
    path.pop()
  }
}

One character — i versus i + 1 — is the entire difference between "each value usable once" and "each value usable any number of times". It is worth saying the sentence out loud before writing the call: does this choice consume the option, or leave it on the table?

path.push(value)
backtrack(, remaining - value)
path.pop()

Pruning is the difference between finishing and timing out

The value > remaining check above is a prune: a branch whose every descendant is guaranteed illegal, cut at the moment that becomes certain. Positive values only grow the sum, so once the running total passes the target nothing deeper can come back. Backtracking without pruning explores a tree of size n^depth; with it, most real inputs explore a fraction. The discipline: prune on a condition that is monotone along the path — a quantity that only increases (sum, length, cost) crossing a bound. If the quantity can come back down, the prune is wrong and eats answers.

How to debug a recursion tree

Indent by depth and print the path at every entry, and the tree becomes a text you can read:

function backtrack(start: number, remaining: number, depth: number): void {
  console.log(`${'  '.repeat(depth)}[ ${path.join(' ')} ] remaining=${remaining}`)
  // ...
}

A branch that shows a value nobody chose is a missing pop. Two branches showing the same prefix where you expected one is a start-index bug — the loop is restarting at 0. An answer set missing an entry while the log shows the branch was visited means the copy happened at the wrong moment, or the base case checked the wrong condition. Six lines of logging answer questions that forty minutes of staring at recursion cannot.

Where this bites

• Recording the path instead of a copy. results.push(path) stores the shared array, and every result row mutates into the last one after the stack unwinds — every row shows the final state, and the test says so confusingly. Counter: push [...path]; the path is scratch space, results are evidence.
• Loop restarting at zero for combinations. Without the start index, every ordering of the same multiset is discovered — output doubles with duplicates that "look correct". Counter: pass i + 1 (or i for reuse) and never 0, unless the question is literally permutations.
• Base case at the wrong depth or value. Recording at path.length === values.length fits permutations and mangles subsets, whose answers live at every depth. Counter: decide where answers live before writing the function — every node (subsets), leaves only (permutations), or a condition on the running total (sum problems).
• Pruning on a non-monotone quantity. Cut on a bound the path can re-enter and you delete legal answers silently — the worst failure mode, because the output looks complete. Counter: only prune what strictly grows; if nothing does, there is nothing safe to prune.