Backtracking is DFS + undo
Backtracking explores a decision tree. At each node, you make a choice (add an element, place a queen, pick a direction). You recurse into that choice, and when you return, you undo the choice (backtrack) to explore other options. The pattern: choose → explore → unchoose. Every backtracking solution has this shape. The key variable is what "choose" and "unchoose" mean for your specific problem.
The universal template
function backtrack(state, choices): if state is a valid complete solution: add to results, return. for each choice in choices: if choice is valid (pruning): make the choice (modify state). backtrack(updated state, updated choices). undo the choice (restore state). The pruning condition is where the problem-specific intelligence lives. Aggressive pruning is the difference between O(n!) and a fast solution.
Pattern 1: Subsets and combinations
Subsets (LC 78): at each position, choose to include or exclude the current element. No pruning needed. Combinations (LC 77): choose k elements from n, must be in order. Start index increments to prevent duplicates. Combination Sum (LC 39): elements can be reused — do not increment start index. Combination Sum II (LC 40): elements cannot be reused AND there are duplicates — sort + skip duplicates at the same level. These 4 problems form a progression that teaches 90% of subset/combination backtracking.
Pattern 2: Permutations
Permutations (LC 46): at each position, any unused element can go. Track used elements with a boolean array. Permutations II (LC 47): with duplicate elements — sort + skip duplicates at the same depth level (same trick as Combination Sum II). Letter Case Permutation (LC 784). Key insight: permutations are harder than combinations because order matters, so you cannot just use a start index — you need a used[] array.
Pattern 3: Board/grid problems
N-Queens (LC 51): place queens one row at a time, prune if column or diagonal is attacked. Sudoku Solver (LC 37): for each empty cell, try digits 1–9, pruning if digit already in row/column/box. Word Search (LC 79): from each cell, DFS in 4 directions, mark visited, unmark on backtrack. These problems have larger state spaces but the same template — the pruning is just more complex.
When NOT to use backtracking
If the problem has optimal substructure (the optimal solution contains optimal solutions to subproblems), use DP instead — it avoids recomputing overlapping subproblems. Backtracking is for problems where you need ALL solutions or where the search space can be pruned aggressively enough to make it practical. Signals that DP is better: "minimum cost", "maximum value", "count the number of ways". Signals that backtracking is right: "generate all", "find any valid arrangement", "is it possible to arrange such that...".