Stop 21 · Data Structures & AlgorithmsTopics · 12/17

Backtracking

In short

Generate all subsets, all permutations, solve Sudoku: backtracking is recursion with an undo button. One template covers most of these questions.

A refinement of recursion that builds a solution incrementally and abandons ('backtracks from') a path as soon as it's known to be invalid — used for permutations, combinations and puzzles.

The purple blob reaches a dead end in a hedge maze and turns back to try another path.

Think of it like this

Walking through a hedge maze

At each fork you pick a path. Hit a dead end? You walk back to the last fork and try the other way. You never restart from the entrance. That walk-back step is the "backtrack".

Watch it happen

All subsets of [a, b]

start: []

take a: [a]

skip a: []

[a, b]

[a]

[b]

[]

1/5First choice: take a. The path is now [a].

The big ideas

What you need to know

Choose

At each step, pick one option and add it to the current path.

Explore

Recurse with that choice made. When the path is complete, save a copy of it.

Un-choose

Remove the last choice and try the next option. This is what makes it backtracking.

Prune early

If a partial path already breaks a rule, like going over the target sum, stop exploring it right away.

See it in code

Walk through the code

1function subsets(nums: number[]): number[][] {2  const result: number[][] = [];3  const path: number[] = [];4 5  function explore(i: number) {6    if (i === nums.length) { result.push([...path]); return; }7    path.push(nums[i]);   // choose: take nums[i]8    explore(i + 1);9    path.pop();           // un-choose: backtrack10    explore(i + 1);       // the other branch: skip nums[i]11  }12 13  explore(0);14  return result;15}

1/3Reached the end? Save a copy of the path. A copy, not the same array.

For n items there are 2ⁿ subsets, so this is O(2ⁿ) by nature. Backtracking can't beat that, but pruning skips useless branches.

Save yourself the pain

Common mistakes

Oops

Pushing path itself into result instead of a copy.

Do this instead

path keeps changing. Push [...path], or every saved answer ends up as the same empty array.

Oops

Forgetting the pop() after the recursive call.

Do this instead

Every push needs a matching pop, or choices from one branch leak into the next.

Your mission

One template, three problems

~45 min

Quick check

In backtracking, what is the purpose of path.pop() after the recursive call?

Go deeper

1Solve classic backtracking problems: subsets, permutations, N-Queens.
2Draw the decision tree for a small backtracking problem by hand first.
3Learn to add pruning (early exit) to avoid exploring clearly invalid branches.