The Decision Tree

The decision tree is the picture behind almost every backtracking solution. A node represents a partial state: the subset chosen so far, the permutation prefix filled so far, the board after several placements, or the string cuts already made. An edge represents one choice that transforms that state into a deeper state.

Leaves are complete candidates. Some leaves become answers, and some are rejected. Good pruning also creates early leaves: places where the algorithm decides that a partial state should not grow any further.

Backtracking does not materialize the whole tree in memory. It performs a DFS walk of the tree. The call stack stores the path from the root to the current node, and each return moves the search back to the parent so another edge can be explored.

This mental model explains why undoing matters. When a recursive call returns from one child, the parent must look exactly as it did before that child was chosen. Otherwise, state from one branch leaks into its sibling branch.

For nums = [1, 2, 3], the root is the empty prefix []. Level one has prefixes [1], [2], and [3]. Under [1], level two has [1, 2] and [1, 3] because only unused numbers can be placed next. The leaves under that branch are [1, 2, 3] and [1, 3, 2].

The same pattern repeats under every first choice. The tree has depth n, and the branching factor shrinks because each level has fewer unused numbers. That is why permutations have factorial growth rather than simple power-set growth.

A decision tree gives you three interview-ready insights. First, it shows the base case: when the node is deep enough to represent a complete candidate. Second, it shows the branching rule: which children a node may have. Third, it shows where pruning can safely remove entire subtrees.

When stuck, draw the tree for the smallest nontrivial input. If you cannot label the root, the children, and the leaves, the state definition is probably not clear enough yet.