Recursion and Backtracking Interview Guide
How to approach recursion and backtracking in interviews — base cases, pruning, and the most common problem types.
Recursion is a mindset, not a trick
Many candidates struggle with recursion because they try to trace every call mentally. The better approach is to trust the recursion: define what a single call does, ensure the base case terminates, and assume recursive calls return the correct result. Once you internalize this, recursion becomes a powerful tool rather than a source of confusion.
Backtracking builds on recursion by exploring choices, undoing them when they lead to dead ends, and trying alternatives. Together, these techniques solve a wide class of interview problems.
The recursion template
Every recursive function follows the same structure: check the base case, do some work, make recursive calls, and return the result. The base case prevents infinite recursion. The recursive case breaks the problem into smaller subproblems.
Thinking recursively
To solve a problem recursively, ask: "If I had the answer to a smaller version of this problem, how would I build the answer to the full problem?" For computing factorial: if I know factorial(n-1), the answer is n * factorial(n-1). For tree height: if I know the heights of both subtrees, the answer is 1 + max(leftHeight, rightHeight).
Common mistakes
Missing or incorrect base cases cause infinite recursion or wrong answers. Forgetting to return the result of recursive calls is another frequent bug. Always verify your base case handles the smallest valid input and that your recursive case makes progress toward it.
Backtracking: the explore-choose-unchoose pattern
Backtracking extends recursion by making a choice at each step, exploring the consequences, and undoing the choice before trying the next option. The pattern is: choose an option, recurse, unchoose (backtrack).
Subsets (LeetCode 78)
Generate all subsets of a given set. At each element, you have two choices: include it or exclude it. Start with an empty subset. For each element, add it to the current subset and recurse (include path), then remove it and recurse (exclude path). Every time you reach the end of the elements, add the current subset to results.
An alternative iterative approach: for each existing subset, create a new subset that includes the current element. Both produce the same result; the recursive approach generalizes better to constrained problems.
Permutations (LeetCode 46)
Generate all arrangements of a set. The key difference from subsets: order matters and every element must be used. Use a visited array or swap-based approach. At each position, try every unused element, recurse to fill the next position, then unmark the element.
Combinations (LeetCode 77)
Choose k elements from n. Similar to subsets, but add to results only when the current combination has exactly k elements. To avoid duplicates, always choose elements in increasing order — the next recursive call starts from the element after the current choice, not from the beginning.
Handling duplicates
"Subsets II" (LeetCode 90) and "Permutations II" (LeetCode 47) add duplicate elements. The key technique: sort the input first. Then, at each level of recursion, skip an element if it equals the previous one at the same level (the previous one was already explored). For permutations with duplicates, the rule is: skip nums[i] if nums[i] == nums[i-1] and nums[i-1] was not used (meaning we already explored the branch that starts with that value).
Constraint satisfaction problems
N-Queens (LeetCode 51)
Place n queens on an n×n board so no two attack each other. Place queens row by row. For each row, try each column. Check if the column, main diagonal, and anti-diagonal are free. If so, place the queen, recurse to the next row, and backtrack. Track occupied columns and diagonals with sets for O(1) lookup.
Sudoku Solver (LeetCode 37)
Find the next empty cell. Try digits 1-9. For each digit, check if it is valid in the current row, column, and 3×3 box. If valid, place it and recurse. If recursion returns false (no valid digit works for a later cell), remove the digit and try the next one. This is pure backtracking with constraint checking.
Word Search (LeetCode 79)
Search for a word in a 2D grid by moving to adjacent cells. Start from every cell that matches the first character. Mark the current cell as visited, try all four directions, and unmark on backtrack. The time complexity is O(m n 4^L) where L is the word length, but pruning makes it fast in practice.
Optimization: pruning
Backtracking without pruning explores the entire search space, which is often exponential. Pruning cuts branches early when you know they cannot lead to a valid solution. For example, in combination sum problems, if the remaining target is negative, stop exploring. In N-Queens, skip columns and diagonals already occupied. Good pruning can reduce runtime from minutes to milliseconds.
When practicing these problems, focus on getting the recursive structure right first, then add pruning. Phantom Coder can help you identify which branches to prune if you are unsure where to optimize.
Practice roadmap
Start with Subsets (78), then Permutations (46), then Combination Sum (39). Move to constrained problems: N-Queens (51) and Word Search (79). Finally, tackle Palindrome Partitioning (131) which combines backtracking with palindrome checking. These six problems build on each other and cover every backtracking pattern you will see.
Ready to ace your next interview?
Phantom Coder gives you real-time AI assistance, invisible to screen sharing.
Download for macOS — $99/mo