What is backtracking?
Backtracking is a technique for finding every possible way to make a series of choices. It builds one answer a single choice at a time — and whenever an answer is finished, or a path turns out to be impossible, it undoes the most recent choice and tries the next option instead. That undo step is the "back" in backtracking.
In this lesson you'll learn the three-beat rhythm every backtracking solution follows, trace it on a small example until it feels mechanical, and write it in code yourself.
Here's a picture to hold onto. Your pizza shop offers three toppings — mushroom, pepperoni, olives — and you want to list every pizza a customer could order, from the plain one to the fully loaded one. Three toppings make 8 possible pizzas, and every extra topping on the menu doubles the count. You can't write one loop per topping, because the menu size isn't fixed.
So let's actually build all 8, in words:
- Write down the plain pizza — no toppings still counts.
- Put mushroom on. That's a pizza — write it down.
- Keep the mushroom and add pepperoni — write down mushroom + pepperoni.
- Keep both and add olives — write down the works. Nothing left to add.
- Stuck. So take the olives back off and look for another topping to try after pepperoni — there is none. Take the pepperoni off too, and try olives straight after mushroom: write down mushroom + olives.
- Keep undoing-and-retrying the same way — pepperoni, pepperoni + olives, olives — until nothing is left to try. 8 pizzas, none missed, none repeated.
Step 5 is the heart of the technique: when a path runs out of new options, undo the last choice and try the next option from that same spot. That undo is the "back" in backtracking — the three beats are always choose (put a topping on) → explore (what can follow it?) → un-choose (take it back off, try the next).
One more connection: the half-built pizza behaves exactly like a stack — the structure from the Stack lesson where you only add and remove at the top. Choosing pushes a topping on; un-choosing pops it off. Now watch the animation run this exact recipe, one push and one pop at a time — keep your eye on the stack.
This section has a step-by-step animation in the interactive lesson.
Quick check
In plain words, what does backtracking do after it finishes exploring one choice?
Answer it in the interactive lesson to keep your progress.
How it works, step by step
Let's slow the pizza machine down and watch every move. We'll list every pizza you can make from
['mush', 'pep', 'oli'].The recipe
- Keep a current pizza — the toppings chosen so far. This is the stack.
- Every state of that pizza is a valid order, so record it the moment you arrive.
- For each topping you haven't considered yet: choose it (
push), explore what can follow (recurse), then un-choose it (pop) and move to the next topping.
Trace it, choice by choice
| step | move | pizza (the stack) | recorded |
|---|---|---|---|
| 1 | start | [] | plain pizza |
| 2 | push mush | [mush] | mushroom |
| 3 | push pep | [mush, pep] | mushroom + pepperoni |
| 4 | push oli | [mush, pep, oli] | the works |
| 5 | pop oli, pop pep | [mush] | — (rewinding) |
| 6 | push oli | [mush, oli] | mushroom + olives |
| 7 | pop oli, pop mush | [] | — (rewinding) |
| 8 | push pep… | [pep] | pepperoni |
Steps 5 and 7 are the backtracks: nothing new to try on this path, so pop back and take the next option. The walk continues until the stack is empty and every topping has been tried from the top — 8 pizzas in all.
Now read the same recipe as code — the three comments are the three beats of the rhythm.
Every Pizza in JavaScript
function everyPizza(toppings) {
const result = [];
function backtrack(start, pizza) {
result.push([...pizza]); // record a COPY of the pizza so far
for (let i = start; i < toppings.length; i++) {
pizza.push(toppings[i]); // choose
backtrack(i + 1, pizza); // explore
pizza.pop(); // un-choose — the backtrack
}
}
backtrack(0, []);
return result;
}
console.log(everyPizza(['mush', 'pep', 'oli']).length); // 8
console.log(everyPizza(['mush', 'pep', 'oli'])[3]); // ['mush','pep','oli']Quick check
The pizza is [mush, pep, oli] and no toppings remain to try. What does it look like two pops later?
Answer it in the interactive lesson to keep your progress.
Same rhythm, new problem: the photo lineup
Here's the payoff for learning the rhythm once: only the choice rule changes between problems.
Three friends — Ana, Ben, Cai — line up for a photo. How many different lineups are there, and what are they? This time the question is about order:
[Ana, Ben] and [Ben, Ana] are different lineups, and a lineup only counts when everyone is in it.Two small changes to the pizza code:
- The choice rule. A pizza never repeats a topping and never looks back (
startmoves forward). A lineup can pick anyone who isn't already standing in it — so instead of a start index, we track who's still remaining. - The recording rule. Every half-built pizza was a valid order, so we recorded at every step. A half-built lineup is not a photo — we record only when nobody is left to place.
Same
push, same pop, same backtrack.Photo Lineups in JavaScript
function lineups(people) {
const result = [];
function backtrack(row, remaining) {
if (remaining.length === 0) { result.push([...row]); return; } // photo complete
for (let i = 0; i < remaining.length; i++) {
row.push(remaining[i]); // choose
backtrack(row, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
row.pop(); // un-choose
}
}
backtrack([], people);
return result;
}
console.log(lineups(['Ana', 'Ben', 'Cai']).length); // 6
console.log(lineups(['Ana', 'Ben', 'Cai'])[0]); // ['Ana','Ben','Cai']Quick check
Why does the lineup version record results only when `remaining` is empty, while the pizza version recorded at every step?
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
Three bugs cause almost every broken backtracking solution:
- Forgetting to undo. If you push a choice and recurse but never pop, the leftover choice leaks into every path explored after it, and all the results are wrong. The undo is not cleanup — it is the algorithm.
- Storing a reference, not a copy.
result.push(path)stores the live array — the one you keep pushing to and popping from. Every stored "result" ends up pointing at the same final state. Store a snapshot:result.push([...path]). - Exploring hopeless branches. If you can already tell a path can't succeed (the sum is too big, the queen is attacked), stop there instead of exploring everything below it. This early cut is called pruning, and on big inputs it's the difference between fast and forever.
Quick check
Storing `path` itself instead of a copy in the results causes…
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Backtracking walks a decision tree — every choice branches into more choices — so its cost is the size of that tree:
| Problem shape | How the tree grows | Space |
|---|---|---|
| include-or-skip (the pizzas) | O(2ⁿ) — doubles with each item | O(n) path + recursion |
| orderings (the photo lineup) | O(n · n!) — multiplies with each item | O(n) path + recursion |
Read those aloud:
O(2ⁿ) means the work doubles every time the menu grows by one; O(n!) grows even faster. That explosive growth is exactly why pruning matters — every branch you cut early removes an entire subtree of wasted work.Note what stays small: you reuse one path array the whole time. The exponential cost lives in the tree of choices, not in memory.
Key takeaways:
- The pattern is always choose → explore → un-choose.
- The undo (pop) is the algorithm; snapshot with
[...path]before recording. - The recording rule belongs to the problem: record every stop (subsets) or only complete answers (orderings).
- Cost tracks the decision tree (
2ⁿ,n!); prune to shrink it.
The textbook versions of what you just learned are waiting in See it: watch Subsets and Permutations animate the classic number versions, and N-Queens show pruning killing whole subtrees. Each also returns as its own practice problem later. Next lesson in the path: Graphs — nodes joined by edges, explored with BFS and DFS.