What it is
Backtracking explores a tree of partial choices — the next element to include, the next cell to step to, the next digit's letter — and abandons a branch the moment it violates a constraint or completes a valid answer, then undoes the last choice and tries the next option at that level. It's exhaustive search with early pruning: you're still visiting every valid possibility (and often many that get cut short), but you never build a complete invalid answer only to throw it away. The technique itself is simple recursion plus "undo state on the way back up"; the actual work is in choosing what state to track and where the constraint check goes.
When it applies
- The problem asks you to enumerate all subsets, permutations, combinations, or arrangements satisfying some constraint, not just count them or find one.
- Choices are made one at a time from a small, well-defined set of options at each step, and a partial choice can be checked for validity before it's complete (a diagonal conflict on a partially placed board, a used-up letter).
- Input sizes are deliberately small (a dozen elements, a handful of digits) — that's the interviewer's signal that exponential exploration is expected, just pruned well.
- If you only need one arrangement's count or feasibility rather than every arrangement, and the subproblems overlap, that's dynamic programming instead — backtracking without memoization would redo the same work. And if there's no constraint to prune against at all, you're just doing brute-force enumeration, which is fine, but calling it "backtracking" adds no value if nothing is ever cut short.
Tells in the problem
- "Return all possible..." combinations, subsets, permutations, or arrangements, as opposed to "return the count" or "return one valid answer."
- A grid or board where a placement (a queen, a letter trace) must be checked against previously placed choices before continuing.
- Deliberately tiny input bounds (n ≤ 10-ish) that would make no sense if a polynomial algorithm existed.
- Duplicate input values paired with a requirement that the output contain no duplicate results — a sign you'll need to skip over repeated choices at the same recursion level.
- A string or array that must be split, arranged, or traced letter by letter or element by element, where each choice narrows what's still admissible.
The classic mistake
A telltale bug shape: marking a board cell used, or appending to a running path, and then moving on to try the next choice without removing that mark or popping that element first. The bug is invisible on the first branch explored (everything looks right until the function backs out), and only surfaces once a sibling branch runs and finds cells or elements still marked from a path that's no longer active. Guard against it by writing the "undo" line immediately after writing the "do" line, before you fill in what happens in between, so cleanup can never be forgotten by the time you add the recursive call.
Questions to start with
- Subsets — the smallest include/exclude decision tree, no pruning needed yet, just the recursive shape.
- Permutations — swaps the choice from "include or not" to "which unused element goes next," introducing a used-tracking set.
- Combination Sum — adds a real constraint to prune against (the running sum) and lets a candidate be reused.
- N-Queens — constraint checking against several previous choices at once (row, column, both diagonals), the sharpest test of early pruning in this hub.
- Word Search — moves the recursion onto a grid, where the "undo" step is un-marking a visited cell rather than popping a list.