What is backtracking?
Backtracking tries a choice, recurses as if it were correct, and undoes it the moment it's proven wrong — or once every path through it has been explored. It's a depth-first walk over a tree of choices, with an explicit undo step built in, so the same state can be reused to try the next option.
- Choice
- One option available at the current step — the thing backtracking tries next
- Path
- The sequence of choices made so far, on the current branch
- Prune
- Abandoning a branch early because a partial path can no longer lead to a valid answer
Why backtracking at all?
Picture trying on outfits. You put one jacket on, check whether the rest of the outfit could still work with it, and if it clashes you take it back off and try the next one — rather than laying out every possible full outfit on the bed ahead of time.
That's backtracking: commit to a choice, explore forward as if it's correct, and undo it the moment it stops working. The undo is what makes it cheap — you never build the whole tree, only the branch you're currently standing on.
Clashes → take it back off. Works → keep it on and move to the next slot.
What kinds of problems does it solve?
Four common shapes. The recursion always looks the same — try, recurse, undo — you only change what counts as a valid choice and when to stop early.
Every subset
At each element, branch into two paths — include it, or don't — then undo and try the other branch.
No early exit, just systematic enumeration of every combination, including the empty one.
Every element is either in the path or it isn't — try both, undo, repeat.
Every ordering
Pick an unused element for the next slot, recurse into the rest, then hand that element back so a
different slot can use it. Same undo, but the choice is which element goes here instead of
in-or-out.
Each element can only be used once per path — undo hands it back for the next branch.
Hit a target, skip what can't work
Sort the candidates first. The moment the running sum plus the next candidate would blow past the target, stop trying candidates at this level entirely — sortedness guarantees every candidate after it is at least as large, so they'd fail too.
Sum would overshoot → prune the rest of this level, no need to even check them.
Trace a path through a grid
Step into a neighboring cell that matches the next letter, mark it visited, and recurse. If the letter doesn't match — or every neighbor is already visited — undo the last step and try a different neighbor.
A mismatched neighbor means undo the step and try a different cell.
Two types
Underneath, it's really only two shapes: backtracking that enumerates everything with no early exit, and backtracking that prunes a branch the instant it can prove that branch is dead.
Generate-everything
There's no shortcut to take — every valid combination is part of the answer, so every branch gets explored. The recursion tries a choice, recurses, and always undoes it afterward to free that choice up for the next branch.
No branch is skipped — every choice is tried, recorded, and undone in turn.
function backtrack(path: number[], choices: number[], out: number[][]): void {
out.push([...path]); // record every path, including the empty one
for (let i = 0; i < choices.length; i++) {
path.push(choices[i]); // try
backtrack(path, choices.slice(i + 1), out); // recurse
path.pop(); // undo — free this choice for the next branch
}
}
Pruned
Before trying a choice, check whether it could possibly still lead to a valid answer. If it can't, skip it — and if sortedness guarantees every later choice is even worse, stop the whole loop right there instead of checking them one by one.
Once a candidate alone would overshoot, every later candidate is bigger still — break, don't just skip.
function backtrack(
path: number[],
start: number,
remaining: number,
candidates: number[], // sorted ascending
out: number[][],
): void {
if (remaining === 0) {
out.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // sorted → every later one is worse too
path.push(candidates[i]); // try
backtrack(path, i + 1, remaining - candidates[i], candidates, out); // recurse
path.pop(); // undo
}
}
Where it works — and where it breaks
Backtracking stays fast when pruning keeps collapsing most of the tree before it's ever built. It breaks down when the branching factor and the depth are both large and nothing can be pruned — the tree of choices just gets too big to walk, no matter how cheap the undo is.
Works with effective pruning
Sorted candidates, target = 7. One overshoot collapses the rest of that branch instantly — the search finds its answer after touching only a handful of the possible paths.
Breaks with no pruning to lean on
Permutations of 4 unconstrained items already means 24 full paths — every one legally has to be explored, because there's no rule that lets you rule any of them out ahead of time.