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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: BFS Layers, Unweighted Shortest Paths, and Multi-Source Search.
Least You Need to Know: BFS Layers, Unweighted Shortest Paths, and Multi-Source SearchRelated lessons
Keep going with nearby lessons in the same topic.