Backtracking
AlgorithmsDFS over the decision tree — build a candidate, abandon it the moment it can't work.
Definition
Backtracking builds a solution incrementally and backtracks — undoes the last choice — the moment a partial candidate can't lead to a valid one. It's a depth-first search over the tree of decisions, with pruning to skip whole branches that violate a constraint.
When to use
Reach for it on combinatorial generation and constraint satisfaction — permutations, subsets, combination sum, N-queens, sudoku, word search. The template is: choose, recurse, then unchoose to restore state before trying the next option.