What is Backtracking?
Backtracking builds one possible answer at a time. At each step, we make a choice, continue with that choice, and remove it when we return.
You only need to be comfortable with recursion and mutable arrays before starting. The short version is: try one choice, finish everything below it, then restore the state and try the next choice.
The Core Idea: Choose and Undo
Take LC 46: Permutations [1,2,3]. The first position can contain 1, 2, or 3. If we choose 1, the next position can contain 2 or 3.
What happens after we finish every permutation beginning with 1? We remove 1 from the current path and try 2 in the first position. That removal is the backtrack.
It is like trying outfits from a small wardrobe. You put on one shirt, try each pair of trousers with it, then put the shirt back before choosing another one.
How One Branch Runs
The Rule You Keep True
The current path must contain exactly the choices made on the route from the root of the search tree to the current node. When a recursive call returns, the path must look exactly as it did before that call.
Permutations and subsets use different choices:
- Permutations choose any value that has not been used in the current path.
- Subsets decide whether to include or skip the next value.
- Constraint problems such as N-Queens reject a choice as soon as it attacks an existing queen.
N-Queens is the one that usually trips us up. The recursion is ordinary backtracking, but the real work is checking columns and diagonals before recursing. Without that early check, we spend most of the time building boards that were already impossible.
Picking the Right Shape
From Rule to Code
- Keep a current path and any state needed to validate the next choice.
- If the path is complete, copy it into the answers.
- Loop through the choices allowed at this depth.
- Add one choice, recurse, and remove that choice after the call returns.
- Skip a branch immediately when it cannot become valid.
Every call either completes an answer or moves one level deeper, and every finite branch eventually returns. The running time follows the number of branches explored, which is often exponential because the output itself is large.
When to use it
- •You need to list every valid arrangement, selection, or path.
- •Each answer is built through a sequence of choices.
- •A choice can be undone before trying the next possibility.
- •The input is small enough that exploring many combinations is expected.
How to identify it
- •The prompt asks for all permutations, subsets, combinations, or board layouts.
- •A partial answer can become invalid before it is complete.
- •The same decision repeats at each depth of a search tree.
- •Words such as choose, arrange, generate, or find every solution appear in the prompt.
Key insights
- →Backtracking follows three actions: choose, explore, and undo.
- →The current path holds one unfinished answer, while completed paths are copied into the result.
- →Undoing a choice restores the exact state needed by the next branch.
- →Pruning stops a branch as soon as it cannot produce a valid answer.
- →The recursion depth usually matches the number of decisions in one complete answer.
Common mistakes
- 01Forgetting to undo a choice, which leaks state from one branch into another.
- 02Saving the same mutable path object instead of copying it when an answer is complete.
- 03Using one choice rule for both permutations and subsets even though they branch differently.
- 04Continuing down a branch after a constraint has already made it invalid.
- 05Expecting polynomial time from a problem that must return exponentially many answers.