Core Concepts

• 1The core template — choose/explore/unchoose: every backtracking solution follows the same three-step loop. (1) Choose: make a decision (add element x to current path, place a queen in column c, etc.). (2) Explore: recurse deeper with that decision made. (3) Unchoose: undo the decision ('backtrack') before trying the next option. This undo step is what separates backtracking from plain DFS. The call stack implicitly manages all the branching — each recursive call handles one decision level, and returning from it automatically leads to the next branch.
• 2Subsets (power set): to generate all 2^n subsets of an array, use a start index to avoid revisiting earlier elements. At each call, the current path is a valid subset — add it to results immediately. Then try adding each element from start..n-1 to extend the path. Crucially, no two calls at the same recursion depth consider the same element — this is enforced by incrementing start. For subsets with duplicates (LC 90), sort first and skip arr[i] == arr[i-1] at the same recursion depth to avoid identical subsets.
• 3Permutations: unlike subsets, permutations use every element exactly once and care about order. The classic approach: maintain a 'used' boolean array. At each depth, try every index not yet used. Choose it (mark used, add to path), recurse, then unchoose (mark unused, remove from path). Total time O(n × n!) — n! permutations each of length n. For permutations with duplicates (LC 47), sort the array and add the pruning condition: skip arr[i] if i > 0 and arr[i] == arr[i-1] and not used[i-1]. This ensures that among duplicate values, the leftmost is always placed first.
• 4Combinations: choose k elements from n without regard to order. The key pruning: at each step, if fewer than (k - path.length) elements remain in [start..n-1], it is impossible to reach size k, so prune. This reduces the constant factor substantially. The upper bound of the for loop is n - (k - path.length) + 1 (1-indexed) or equivalently n - (k - len(path)) (0-indexed with exclusive end). Combination sum (LC 39) allows reuse of the same element — pass the same index i (not i+1) when recurring. Combination sum II (LC 40) forbids reuse and has duplicates — sort and skip duplicates at the same depth.
• 5N-Queens: place n queens on an n×n board such that no two queens share a row, column, or diagonal. The key insight: since we place exactly one queen per row (recurse row by row), we only need to check column conflicts and diagonal conflicts. Track three sets: cols (occupied columns), diag1 (occupied r-c diagonals — same value for '/' diagonals), diag2 (occupied r+c diagonals — same value for '\' diagonals). A position (r, c) is safe if c not in cols, r-c not in diag1, r+c not in diag2. This reduces per-placement check from O(n) to O(1). Total solutions: 1, 0, 0, 2, 10, 4, 40, 92 for n=1..8.
• 6Sudoku solver: the constraint propagation + backtracking combination. For each empty cell, try digits 1-9. Check row, column, and 3×3 box constraints. If valid, place the digit and recurse to the next empty cell. If the recursive call returns False (no solution found), remove the digit and try the next. The pruning is implicit: invalid placements are never explored. Optimization: always pick the empty cell with the fewest valid options (minimum remaining value heuristic) — this can reduce the search space by orders of magnitude.
• 7Word search on a grid: given a 2D grid and a word, determine if the word exists as a connected path (4-directional, no reuse). Start DFS from every cell that matches word[0]. Mark the current cell as visited (e.g., temporarily set to '#') before recursing to prevent reuse within the current path, then restore it after. Pruning: if word[0] appears far fewer times than word[-1], reverse the word — searching from the rarer end prunes the search tree much earlier.
• 8Palindrome partitioning (LC 131): partition a string s into substrings such that every substring is a palindrome. Enumerate all possible first substrings s[0..i] for i from 0 to n-1. If s[0..i] is a palindrome, add it to the path and recurse on s[i+1..]. Precompute a 2D palindrome table dp[i][j] in O(n²) to check is_palindrome in O(1) during backtracking. Letter combinations of phone number (LC 17): for each digit, map it to its letters and recurse through the remaining digits — this is the simplest tree of choices.
• 9Time complexity of backtracking: always exponential in the worst case — O(2^n) for subsets, O(n!) for permutations. In practice, pruning eliminates enormous portions of the search tree. The actual runtime depends heavily on the constraints. When discussing complexity in an interview, state the worst-case bound and then explain what pruning does: 'In the worst case O(n!) but pruning eliminates invalid branches early, making it feasible for n ≤ 20 or so.' For N-Queens, the actual number of solutions grows much slower than n! — the constraint propagation keeps the tree manageable.

Key Patterns & Templates