Backtracking

Build candidates incrementally and abandon a path the moment it cannot lead to a valid solution — a disciplined, pruned DFS over the choice space.

Key ideas

  • —Choose, recurse, then undo the choice — the "undo" is what makes it backtracking.
  • —Prune as early as possible; a good constraint check turns exponential into tractable.
  • —Subsets, permutations, and combinations are three views of the same template.

The choose / explore / unchoose loop

At each step you make a choice (add an element, place a queen), recurse to extend the partial solution, then undo the choice so the next iteration starts clean. That explicit undo keeps a single mutable path instead of copying state everywhere, and it is the structural difference between backtracking and plain enumeration.

Pruning is the whole game

Brute force over all arrangements is exponential, so the value of backtracking comes from cutting branches early. In N-Queens you reject a column or diagonal the instant it conflicts; in Combination Sum you stop once the running total exceeds the target. The earlier and cheaper the check, the more of the tree you avoid.

Practice this

Sources

← All lessonsNext: Greedy Algorithms →