Backtracking

Explore a decision tree incrementally and undo state when a branch stops being viable.

Explore a decision tree incrementally and undo state when a branch stops being viable.

The current path always represents a valid partial solution that satisfies all constraints up to the current depth.

Pruning invalid branches early avoids expanding the full exponential tree.

Undoing state after each branch keeps memory usage proportional to recursion depth, not total branches.