What backtracking is
Your pizza shop offers three toppings — mushroom, pepperoni, olives — and you want to list every pizza a customer could order, from a plain one all the way to the fully loaded one. Three toppings make 8 pizzas;
n toppings make 2ⁿ. You could nest loops, but n isn't known when you write the code, so a fixed stack of loops can't work.Backtracking builds each answer one choice at a time. At every step it:
- chooses an option (add a topping to the pizza)
- explores everything that follows (what else could we add?)
- un-chooses it (take that topping back off) and tries the next option
Here's the key: the half-built pizza is a stack. Choosing pushes a topping on top; un-choosing pops it back off. That push/pop rhythm — choose → explore → un-choose — is the whole idea. The animation builds all 8 pizzas 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
After exploring a choice, backtracking must…
Answer it in the interactive lesson to keep your progress.
How it works, step by step
Now let's turn that push/pop rhythm into code. We'll generate every subset of
[1, 2, 3] (the same shape as the pizzas — an item is either on the path or not).The steps
- Keep a current path — the choices made so far (this is the stack).
- Record the current path as one result.
- For each remaining choice: choose it (
push), explore by recursing, then un-choose it (pop— this is the backtrack). - When a branch runs out of choices, it unwinds back up to try the next one.
Trace it on [1, 2, 3]
| step | action | path (stack) | recorded |
|---|---|---|---|
| 1 | start | [] | {} |
| 2 | push 1 | [1] | {1} |
| 3 | push 2 | [1,2] | {1,2} |
| 4 | push 3 | [1,2,3] | {1,2,3} |
| 5 | pop, pop | [1] | — |
| 6 | push 3 | [1,3] | {1,3} |
…and so on until the stack empties. Every state the stack passes through is one subset. In JavaScript, the same steps read like this:
function subsets(nums) {
const result = [];
function backtrack(start, path) {
result.push([...path]); // record a COPY of the current path
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose
backtrack(i + 1, path); // explore
path.pop(); // un-choose — the backtrack
}
}
backtrack(0, []);
return result;
}
console.log(subsets([1, 2, 3])); // [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]Quick check
Path is [1, 2, 3] and no choices remain. Predict the path two steps later.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Forgetting to undo. If you push a choice and recurse but never pop, the path leaks into sibling branches and every result is wrong. The undo is not optional — it is the algorithm.
- Storing a reference, not a copy.
results.push(path)stores a live array that later mutations will change. Push[...path]— a snapshot. - No pruning. Exploring branches that cannot possibly succeed wastes enormous time. Cut them early (bound checks, used-sets) whenever the problem allows.
Quick check
Storing `path` itself instead of a copy in the results causes…
Answer it in the interactive lesson to keep your progress.
You learned it — now apply it to a new problem
You just generated subsets with choose → explore → un-choose. Here's the payoff: the exact same rhythm solves a brand-new problem with only the choice rule changed. Instead of "include this item or not," a permutation asks for every ordering: at each step pick any unused item, recurse on what's left, then put it back. When nothing remains, the path is one complete ordering.
Same
push / pop, same backtrack — different question. All orderings of [1, 2, 3]:function permutations(nums) {
const result = [];
function backtrack(path, remaining) {
if (remaining.length === 0) { result.push([...path]); return; }
for (let i = 0; i < remaining.length; i++) {
path.push(remaining[i]); // choose
backtrack(path, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
path.pop(); // un-choose
}
}
backtrack([], nums);
return result;
}
console.log(permutations([1, 2, 3])); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Quick check
Same rhythm, new choice rule. Predict how many results permutations of [1, 2, 3] records.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, backtracking explores a decision tree, so its cost is the size of that tree:
| Problem shape | Decision tree size | Space |
|---|---|---|
| subsets | O(2ⁿ) — each item in or out | O(n) path + recursion |
| permutations | O(n · n!) — every ordering | O(n) path + recursion |
You reuse one path array instead of building every candidate up front — the exponential cost is all in the tree, not the memory.
That exponential cost is why pruning matters — cutting hopeless branches early is often the difference between fast and forever.
Key takeaways:
- The pattern is always choose → explore → un-choose.
- The undo (pop) is the algorithm; snapshot with
[...path]before recording. - Cost tracks the decision tree (
2ⁿ,n!); prune to shrink it.
This backbone drives the hardest-looking interview problems, each its own lesson later (no need to know them yet): permutations & combinations, N-Queens & Sudoku (place, recurse, remove on conflict), and word search / combination sum (explore a grid or a target, pruning dead ends). Next up in order: Graphs — nodes joined by edges, explored with BFS and DFS.