Backtracking
Explore all possibilities via recursion, but prune branches that cannot lead to valid solutions. Build the solution incrementally and undo choices when they lead to dead ends.
Time
O(n!) worst case
Space
O(n) recursion depth
Recognize it when
- Generate all valid combinations/permutations
- Constraint satisfaction (Sudoku, N-Queens)
- Word search in grid
- "Find all solutions" problems
Questions — ordered by difficulty
Combination Sum
Find all combinations of candidates that sum to target. Numbers can be reused.
Word Search
Find if a word exists in a 2D board by connecting adjacent (not diagonal) cells.
N-Queens
Place n queens on an n×n chessboard such that no two queens attack each other. Return all valid arrangements.
Sudoku Solver
Solve a Sudoku puzzle by filling in the empty cells.
Generate Parentheses
Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Palindrome Partitioning
Partition a string such that every substring is a palindrome. Return all possible partitions.