The unifying picture
Every backtracking problem can be drawn as a state space tree. The root is the empty partial solution. Each edge represents one decision, and each node is the partial candidate built so far. Leaves are complete candidates, either valid solutions or dead ends.
Reading the tree
- The depth of a node equals the number of decisions made.
- The branching factor at a node is the number of choices available there.
- A solution is a path from the root to an accepting leaf.
- Backtracking is simply a depth-first traversal of this tree, with pruning that snips subtrees you can prove are fruitless.
Why the model helps
Thinking in terms of the tree clarifies design questions. The number of leaves bounds the worst-case work. Where you place validity checks decides how high pruning happens. Choosing which decision to make at each level, and in what order, reshapes the tree to expose failures sooner. Many problems differ only in what a node stores and what makes a leaf accepting.
Key idea
A state space tree casts backtracking as a depth-first walk where nodes are partial candidates and leaves are complete ones, making pruning, ordering, and cost all easy to reason about.