Algorithms / Backtracking State Space
Least You Need to Know: Backtracking as Search Over Partial Choices
Backtracking explores a **state space of partial decisions**. The key idea is to build a candidate step by step, detect impossible or completed states early, and undo choices cleanly when a branch cannot lead to a valid answer.
The least you need to know
- A backtracking state usually represents a partial assignment, not a fully solved output yet.
- Each recursive call chooses one more decision, explores its consequences, and then undoes that choice before trying the next branch.
- A complete valid assignment is a base case that can be recorded or returned immediately.
- If a partial state already violates a requirement, the entire branch can be abandoned.
- Backtracking is most natural when the prompt asks you to enumerate or search through constrained combinations of choices.
Key notation
state
current partial assignment being explored
choose / explore / unchoose
make one decision, recurse, then undo it
solution
a complete state that satisfies all constraints
Tiny worked example
- To generate valid choices, start from an empty partial state.
- Pick one candidate decision and add it.
- Recurse on the smaller remaining problem.
- When the recursive call returns, undo that decision so the next branch starts from a clean state.
Common mistakes
- Students often forget the undo step and accidentally let one branch corrupt the next branch.
- Students often try to prune using conditions that are only checkable after completion, which loses valid solutions.
- Students often describe backtracking as random guessing even though it is structured search over partial states.
How to recognize this kind of problem
- The prompt asks you to generate all valid arrangements or search for one valid arrangement under constraints.
- A partial answer can already be declared impossible before all positions are filled.
- There is a natural recursive tree where each level corresponds to one more decision.