What is Backtracking
Backtracking builds candidates one choice at a time and abandons a partial candidate as soon as it cannot lead to a valid solution.
The Core Idea
Backtracking is depth-first search over possible configurations. Instead of trying to guess the final answer directly, you build a partial candidate step by step. At each step, the algorithm asks which choices are legal from the current partial state, commits to one choice, explores the consequences, and then returns to try the next choice.
The word backtrack means retreating from a partial candidate when it is complete, invalid, or no longer useful. The retreat is not failure; it is the mechanism that lets one recursive search reuse the same state container for many alternatives.
Incremental Construction
A backtracking solution treats the answer as something constructed gradually: a path of chosen numbers, a set of used positions, a partially filled board, or a string being partitioned. The current partial object is the state that the next recursive frame extends.
This is why backtracking feels different from many iterative algorithms. The central action is not scanning once from left to right. The central action is asking: what can I safely add next, and what must become true before I can record a complete answer?
Backtracking vs Enumerate Then Filter
A brute-force enumerate-then-filter approach generates every complete candidate first and checks validity at the end. That is often wasteful because many candidates contain an invalid prefix that could have been rejected much earlier.
Backtracking moves the validity checks into the construction process. If a partial board already has two queens attacking each other, there is no reason to place the remaining queens. If a partial sum already exceeds a positive target, deeper choices cannot repair it. Abandoning these branches early is what turns a naive exponential idea into a practical interview solution.
The Interview Mental Model
In interviews, describe backtracking with three nouns: state, choices, and base case. The state is what the current recursion frame knows. The choices are the legal next moves from that state. The base case is the point where the partial candidate becomes complete enough to record or reject.
Once those are clear, the implementation usually follows the same rhythm: choose one option, recurse to explore it, then undo that choice so the next option starts from a clean state.
Subset search as incremental construction
The path is the partial candidate. Each recursive frame decides whether the next value belongs in that candidate before moving deeper.
Key Takeaways
- Backtracking is DFS over configurations, not a separate data structure.
- The algorithm builds partial candidates and rejects dead branches before they become full candidates.
- A backtracking explanation should name the state, choices, base case, and rejection rule.
- Compared with enumerate then filter, backtracking moves validity checks earlier in the search.