Backtracking
Build a candidate one choice at a time, and undo the last choice the moment it cannot lead anywhere.
Backtracking is depth-first search over partial answers. Make a choice, recurse, and when the recursion returns, undo the choice before trying the next one. The undo is what separates it from plain enumeration: one board, one array and one visited set are reused at every node of the tree, so the memory is the depth of the search rather than the number of candidates in it.
The search space is whatever it is: 2^n subsets, n! permutations, nine choices per empty Sudoku cell. Backtracking does not shrink those numbers. What it does is refuse to extend a candidate that is already impossible, a queen that is attacked or a running sum that has overshot the target, and every rejection at depth d deletes the entire subtree below it. That pruning is the difference between a board solved in milliseconds and one that never finishes.
So the design question is how early a constraint can be tested. The test runs at every node and has to earn its cost in branches removed. N-Queens checks one column and two diagonals in constant time per placement and kills whole subtrees with it; a check that only works on a finished candidate prunes nothing at all and leaves you with brute force.
After this you can
- Write the choose, explore, undo loop and say exactly what the undo restores
- Enumerate subsets, permutations and combinations without producing a duplicate
- Place a constraint check at the point in the tree where it cuts the most branches
- Bound a search by the shape of its tree: branching factor raised to the depth
The list starts with 3. Keep it, and call sum on the remaining 4 numbers. A smaller problem each time.
In this order
- RecursionA function that calls itself on a smaller input until a base case, each call parked as a frame until the one above it returns.
- BacktrackingBuild a solution one choice at a time and undo the last choice when it cannot lead to a solution.
- SubsetsInclude or exclude each element in turn; every leaf of that binary tree is one subset, 2^n in all.
- PermutationsSwap each remaining element into the next position, recurse, and swap back; n! leaves.
- CombinationsChoose k of n in increasing index order so each combination appears once; prune when too few remain.
- Combination SumChoose candidates with reuse, in non-decreasing order, until the sum hits the target; prune the moment a pick would overshoot.
- Rat in a MazeMove through open cells toward the exit; retreat from dead ends.
- Word SearchDFS from each cell holding the first letter, extending through neighbours that hold the next one; cells on the path are used once.
- N-QueensPlace one queen per row; a column or diagonal conflict forces backtracking.
- Constraint Search and PruningChecking a constraint at each placement prunes whole subtrees before they are explored.
- Sudoku SolverFill empty cells with a digit that satisfies row, column and box; backtrack on dead ends.
Where people go wrong
Forgetting the undo
Whatever was changed on the way down has to be restored on the way up: pop the element, clear the visited cell, unset the column. A missing undo does not crash, it silently blocks branches that were never really used and you get too few answers.
Duplicates from unordered choices
Picking any remaining element at each level produces every combination k! times over. Only ever picking an index larger than the last is what makes each one appear once, and sorting first is what lets you skip equal siblings at the same level.
Checking after the candidate is complete
Building a full assignment and then validating it is brute force with extra bookkeeping. The check has to run on the partial candidate, before the recursive call, or no subtree is ever cut.
Or a different category
Dynamic Programming
You want one best answer over overlapping subproblems rather than every answer; the table replaces the tree.
Greedy
Each step has a provably safe choice, so there is nothing to undo and no tree to search.