Backtracking
Recursive brute-force search with early pruning — build a partial solution, and abandon it the moment it can't possibly work.
What it is
Backtracking explores a decision tree of partial solutions depth-first: at each step, try a choice, recurse, and if that path doesn't lead anywhere valid, undo the choice ("backtrack") and try the next one.
The template
- If the partial solution is complete, record it.
- Otherwise, for each candidate next choice: make the choice, recurse, then undo the choice before trying the next candidate.
Pruning is what makes it tractable
Without pruning, backtracking is just exhaustive brute force. The speedup comes from cutting a branch as soon as it's provably invalid (e.g. a placed queen already attacks another) rather than completing it and checking at the end.
Complexity
Worst case is exponential (it's exploring a full decision tree), but effective pruning can cut the explored space dramatically. Backtracking is the right tool when the problem is "generate all valid configurations" or "does any valid configuration exist," not when a greedy or DP approach can guarantee an answer without exploring alternatives.
Where it shows up
Permutations/combinations, N-Queens, Sudoku solving, and subset-sum-style problems.