What backtracking is
Backtracking is a refined brute force. You build a candidate solution one piece at a time, and the moment a partial candidate cannot possibly extend to a valid answer, you abandon it and step back. That early abandonment is what separates it from blind enumeration.
The universal skeleton
Almost every backtracking routine follows the same three-step rhythm at each decision point:
- Choose a candidate value for the current position.
- Explore deeper by recursing into the next position.
- Un-choose by undoing the change so the next candidate starts clean.
Wrapped around that is a base case that records a finished solution, and a validity check that rejects bad choices before recursing.
Why the un-choose matters
The recursion typically mutates a single shared structure, such as a path list or a board. After exploring one branch you must restore the structure exactly as it was, or the next sibling branch will inherit stale state. Forgetting this undo is the most common backtracking bug.
Key idea
Backtracking is choose, explore, un-choose around a recursive call, pruning dead branches early so you explore far fewer candidates than full enumeration would.