If you have already worked through two pointers, BFS/DFS, and dynamic programming, there is one pattern left that separates candidates who freeze on hard problems from those who calmly work through them: backtracking. It powers some of the most frequently asked interview questions at Google, Amazon, Meta, and Microsoft — from generating subsets to solving N-Queens. In this walkthrough, we break down the backtracking pattern for coding interviews, give you a reusable template, and cover the six problems you must know in 2026.
What Is Backtracking?
Backtracking is a systematic way to explore all possible solutions to a problem by building candidates incrementally and abandoning a path the moment it cannot lead to a valid answer. Think of it as depth-first search over a decision tree: at every node you make a choice, explore its consequences, and if the path fails, you undo the choice and try the next option.
The mental model interviewers expect you to articulate has three steps, repeated recursively:
- Choose — add a candidate element to the current partial solution.
- Explore — recurse deeper with the updated state.
- Undo — remove the element so the next iteration starts clean.
The Universal Backtracking Template
Nearly every backtracking problem fits this skeleton. Memorize the shape, not the specific problems:
def backtrack(path, choices):
if is_solution(path):
results.append(path.copy()) # record a deep copy
return
for choice in choices:
if not is_valid(choice, path):
continue # prune early
path.append(choice) # 1. choose
backtrack(path, next_choices) # 2. explore
path.pop() # 3. undo
Two details matter in interviews. First, always append a copy of the path when recording results — appending the mutable list itself is the single most common backtracking bug. Second, pruning invalid branches early (constraint checks before recursing) is what turns a brute-force answer into an accepted one.
How to Recognize a Backtracking Problem
Reach for backtracking when the problem asks for all combinations, permutations, partitions, or paths — not just a count or an optimum. Key phrases include "return all possible", "generate every valid", and "find all ways to". If the question only wants the number of ways or the best value, dynamic programming is usually the better tool. If it wants the solutions themselves, backtracking is your pattern.
The 6 Backtracking Problems You Must Know
1. Subsets (LeetCode 78)
The canonical starter. At every index you make a binary decision: include the element or skip it. Record the path at every node, not just at the leaves. Time complexity is O(n · 2ⁿ) because there are 2ⁿ subsets and copying each costs up to O(n).
2. Permutations (LeetCode 46)
Instead of moving left to right, every unused element is a valid next choice. Track usage with a boolean array or a set. Expect the follow-up on handling duplicates (LeetCode 47): sort first, then skip a duplicate unless its twin was used at the same depth.
3. Combination Sum (LeetCode 39)
Introduces two twists: elements can be reused, and you prune when the running sum exceeds the target. Passing a start index prevents duplicate combinations — a detail interviewers specifically probe.
4. Word Search (LeetCode 79)
Backtracking on a 2D grid. Mark a cell as visited before recursing into its four neighbors, then restore it on the way out. This problem tests whether you truly understand the undo step, because forgetting to restore the cell silently breaks sibling branches.
5. Palindrome Partitioning (LeetCode 131)
Combines backtracking with string validation: at each position, try every prefix that forms a palindrome and recurse on the remainder. The advanced follow-up memoizes palindrome checks — a nice bridge between backtracking and DP worth mentioning to your interviewer.
6. N-Queens (LeetCode 51)
The classic hard problem. Place one queen per row, and prune using three sets: occupied columns, and the two diagonal identities (row − col and row + col). If you can code N-Queens cleanly in 20 minutes, you are ready for any backtracking question a FAANG interview throws at you.
Complexity: What to Say When Asked
Backtracking complexities are exponential by nature, and interviewers want you to say so confidently: O(2ⁿ) for subsets, O(n · n!) for permutations, and O(4ⁿ·ᵐ) in the worst case for grid search with path length m. Then immediately explain how pruning cuts the practical search space — that follow-through is what earns senior-level signal.
A 5-Day Backtracking Practice Plan
Day 1: Learn the template and solve Subsets and Subsets II. Day 2: Permutations I and II — focus on the duplicate-skipping rule. Day 3: Combination Sum I and II plus Letter Combinations of a Phone Number. Day 4: Word Search and Palindrome Partitioning to master state restoration. Day 5: N-Queens and Sudoku Solver under a 40-minute timer, explaining your pruning out loud as you code.
Common Mistakes That Cost Offers
Watch for the four failure modes that appear again and again in real interviews: appending the mutable path instead of a copy, forgetting to undo state after recursion (especially on grids), missing the start-index trick and generating duplicate combinations, and skipping pruning so the solution times out on large inputs. Rehearse the choose–explore–undo vocabulary until you can narrate it naturally — interviewers grade your reasoning as much as your code.
Start Practicing Today
Backtracking looks intimidating until the template clicks — then an entire class of "hard" problems becomes mechanical. Block out five days, work through the problems above in order, and practice explaining every choice out loud the way you would in a real interview. Pair your practice with mock interviews and tools like Niraswa AI to pressure-test your explanations before the real thing. Your next offer may hinge on a clean N-Queens — make sure you have already solved it twice.
