Recursion & Backtracking Questions
Backtracking is the systematic technique for exploring all possibilities and pruning invalid paths early. These problems appear heavily at Google and Meta and require strong recursive thinking.
Sample Questions & Strong Answers
Subsets — generate all possible subsets of a set.
Backtrack: at each index, choose to include or exclude the current element. Recurse with next index. Add current path to result at every call (not just leaves). Time O(2^n × n), Space O(n) recursion depth. Iterative: for each element, append it to all existing subsets.
Pro tip: Add to result at every node (not just leaves) — this is the difference from Combination/Permutation. Amazon, Google, Meta.
Permutations — generate all permutations of a list.
Backtrack: maintain a 'used' boolean array. At each depth level, try all unused elements, mark used, recurse, unmark. Leaves (depth === n) are complete permutations. Time O(n! × n), Space O(n). For duplicates: sort first and skip same-value elements at same depth.
Pro tip: The 'used' array or in-place swap are both valid approaches. For no-duplicates input, swap-based is cleaner. Amazon, Google, Meta, Microsoft.
Combination Sum — find all combinations of numbers that sum to target (unlimited use).
Backtrack starting at index i. At each step: add candidates[i] and recurse with same i (unlimited use). Or skip to i+1. Prune when sum > target. Sort candidates first to enable early termination. Time O(2^(T/M)) where T=target, M=min candidate.
Pro tip: Starting recursion from same index i (not i+1) enables unlimited use. This is the key difference from Combination Sum II. Amazon, Google.
Letter Combinations of Phone Number.
Backtrack: for each digit, iterate its mapped letters. Append to current path, recurse with next digit, pop. Base case: path length equals digits length → add to result. Time O(4^n × n) where n=digits length, Space O(n).
Pro tip: Map digits 2–9 to letter groups. 7 and 9 have 4 letters. This is a clean DFS through a decision tree — often used as a backtracking intro. Amazon, Meta, Google, Microsoft.
Generate Parentheses — generate all valid n-pair parentheses combinations.
Backtrack with open and close counters. Add '(' if open < n. Add ')' if close < open. At n pairs, add to result. Time O(4^n / √n) — Catalan number, Space O(n) depth.
Pro tip: The invariant 'close < open' ensures validity without checking the full string. Amazon, Google, Meta, Microsoft — medium, commonly asked.
Word Search — find if word exists in 2D grid using adjacent cells.
DFS from each cell. Mark cell as visited (e.g., swap with '#'), recurse in 4 directions, restore on backtrack. Base case: index === word.length. Prune: out of bounds, wrong character, already visited. Time O(m×n×4^L) where L=word length.
Pro tip: Restoring the cell on backtrack (instead of a separate visited matrix) saves space. Amazon, Meta, Microsoft.
N-Queens — place N queens on N×N board with no attacks.
Backtrack row by row. Track used columns, left diagonals (row−col), and right diagonals (row+col) in sets. At each row, try each column: if not attacked, place queen, recurse to next row, remove from sets. Time O(n!), Space O(n).
Pro tip: Three sets (columns, '/', '\' diagonals) enable O(1) attack checks. The diagonal key insight: all cells on a '/' diagonal have the same row−col value. Amazon, Google — hard.
Palindrome Partitioning — partition string so all substrings are palindromes.
Backtrack: try all partitions starting at current index. If s[start..end] is palindrome, add to path and recurse from end+1. Precompute palindrome table (DP) for O(1) checks. Time O(2^n × n), Space O(n² + n) with DP table.
Pro tip: Precomputing the isPalindrome table with DP makes each check O(1) instead of O(n). Without it, worst case is O(n^3). Amazon, Google.
Sudoku Solver — fill a Sudoku board.
Find empty cell. Try digits 1–9: check if valid in row, column, and 3×3 box. Place digit, recurse. If recursion returns false, unplace (backtrack). Return true when no empty cells remain. Time O(9^(n empty cells)), Space O(1).
Pro tip: Use three sets (rows, cols, boxes) for O(1) validity checks. Box index = (row/3)*3 + col/3. Amazon, Microsoft — hard.
Combinations — generate all combinations of k numbers from 1 to n.
Backtrack: start from index start, choose elements. When path length equals k, add to result. Pruning: if remaining elements < needed, stop early. Time O(C(n,k) × k), Space O(k) depth.
Pro tip: Pruning: if n − start + 1 < k − path.length, not enough elements remain. This cuts significant branches. Amazon, Google, Microsoft.
Expert tips
Backtracking template: choose → explore → unchoose (undo). The undo step is what distinguishes backtracking from DFS.
Prune early: check constraints before recursing, not after — this cuts the tree significantly.
For duplicate handling: sort first, then skip same-value elements at the same recursion level (not across levels).
Time complexity for backtracking is usually O(branching factor^depth × work per node) — exponential, but pruning makes it practical.
Related interview topics
Recursion & Backtracking Questions FAQ
Practice Recursion & Backtracking Questions with real-time AI.
Stop reading sample answers and start practicing. Get personalized feedback on structure, delivery, and depth — every time.
Free plan available · No credit card needed · Cancel anytime