Backtracking: how to spot it
We'll cover the following
Build an answer one choice at a time. If a choice leads nowhere, undo it and try the next one. It is a depth-first search over all possibilities, made fast by pruning branches that cannot work.
How the question sounds
- List all subsets, permutations, or combinations
- Generate all valid arrangements (parentheses, queens, sudoku)
- Word search or path problems where you may need to undo a move
- A choice, then explore, then undo (choose, explore, unchoose)
- The answer is "all possible ways", not just a count
The two shapes
Where it shows up in GenAI work
Constrained and grammar-guided decoding explores token choices and discards ones that break the schema. Planning agents and tree-of-thought style search expand candidate steps and prune weak branches. Prompt or configuration search tries combinations and rolls back the bad ones.
Is it backtracking?
Decide yes or no before you open each answer.
Check yourselfList all subsets of an array.
Yes. Include or exclude each item, undoing between branches.
Check yourselfGenerate all valid combinations of n pairs of parentheses.
Yes. Add a bracket if it keeps the string valid, then undo.
Check yourselfPlace 8 queens so none attack each other.
Yes. Place, check constraints, backtrack on dead ends.
Check yourselfCount the number of ways to climb n stairs.
No. You only need a count, and sub-problems repeat. That is dynamic programming.
Check yourselfFind the shortest path in a maze.
No. BFS finds the shortest path directly.
Check yourselfFind a target in a sorted array.
No. Binary search.
Problems in this pattern
- Subsets · Medium · Include or exclude
- Permutations · Medium · Fill the slots
- Combination sum · Medium · Prune early
- N-Queens · Hard · Constraint search
Summary: say it in the interview
- Choose, explore, undo: Make one choice, recurse on the rest, then remove the choice so the next option starts clean.
- Prune: Stop a branch as soon as it cannot lead to a valid answer. That is what keeps the search fast.