Backtracking
Hard+110 XPExplore choices as a decision tree — make a choice, recurse, then UNDO it and try the next one.
No visualization loaded.
Watch
—
Press Run to begin.
Backtracking is how you explore every possible combination of choices without losing your place. You make a choice, dive deeper, and when that path is fully explored you UNDO the last choice and try the next option — like walking a maze, marking dead ends, and stepping back to the last fork. Here we generate every subset of [1, 2, 3]: for each number we choose INCLUDE or SKIP, and the tree of all those choices has one leaf per subset.
▸What is backtracking, in plain words?
It's organised trial-and-error. You build an answer one choice at a time. At each step you try an option and recurse. If you reach a complete answer you record it; either way, when you've finished exploring under a choice, you UNDO that choice and try the next one. This naturally walks a 'decision tree' — every path from the root to a leaf is one complete set of choices.
▸How is it different from brute force?
Pure brute force builds every candidate from scratch and checks it. Backtracking reuses the work in progress: it grows ONE partial answer, sharing the common prefix between sibling branches, and — crucially — it can PRUNE. The moment a partial choice can't possibly lead to a valid answer, it stops and backs out instead of finishing a doomed path. That pruning is what makes it beat blind brute force on problems like N-Queens.
▸What does 'undo the choice' actually mean?
It means putting the world back exactly how it was before you made the choice, so the next option starts clean. Here, after exploring the 'INCLUDE 2' branch we POP the 2 back off the current subset before exploring 'SKIP 2' — otherwise the 2 would leak into branches where we never chose it. Make the choice on the way down, undo it on the way back up. That mirror image is the whole trick.
▸Where is backtracking used?
Puzzle and constraint problems: solving Sudoku, placing N queens so none attack each other, generating all permutations or combinations, the subset-sum and knapsack searches, maze and word-search solving, and parsing/expression problems. Anytime the answer is built from a sequence of choices and you must explore them systematically, backtracking is the pattern.
How the work grows
O(2^n) — two choices per element is avoid — explodes almost immediately. For subsets, each of the n elements is a 2-way fork (include or skip), so the tree has 2^n leaves and the work grows exponentially. The memory is small though: at any instant we only hold one root-to-leaf path — O(n) deep — plus the partial answer being built.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.