Overview

Medium

Choose → explore → un-choose

In simple words

Try a choice, go deeper, and if it fails, undo it and try the next — like exploring a maze and backing up at dead ends.

The idea

Build a solution incrementally. At each step make a choice, recurse to extend it, then undo the choice before trying the next one. Pruning invalid branches early keeps it fast.

←→stepspaceplay

★

1/7

Optimal

timeexponentialspaceO(depth)

The universal shape.

1function backtrack(path, choices) {2  if (isComplete(path)) { record(path); return; }3  for (const c of choices) {4    if (!valid(c)) continue;5    path.push(c);          // choose6    backtrack(path, next); // explore7    path.pop();            // un-choose8  }9}

Input

grid: 3 × 3

Memory

at: —
cells marked: 0
step: —
blocked: —

Output

goal: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: subsets of [1, 2]
Output:: [], [1], [1,2], [2]
Explanation:: At each element choose take or skip, recurse, then un-choose. Four leaves for two elements, 2ⁿ in general.

Example 2

Input:: permutations of [1, 2, 3] with 1 fixed first
Output:: [1,2,3], [1,3,2]
Explanation:: Marking 1 as used prunes the whole branch where it appears again — the pruning is what keeps backtracking usable.

Finished the walkthrough? Add it to your streak.