If binary search is the pattern interviewers use to test precision, backtracking is the one they use to test how you think under open-ended constraints. Subsets, permutations, combination sum, word search, N-Queens — these problems appear constantly in interviews at Google, Amazon, Microsoft, and fast-growing startups, and they all collapse into a single reusable template once you see the underlying structure.
This guide breaks down the backtracking pattern for 2026 interviews: how to recognize it, the universal template that solves 90% of these problems, the five classic problems you must know, and the pruning techniques that separate a pass from a strong hire.
What Is Backtracking, Really?
Backtracking is structured brute force. You build a candidate solution one choice at a time, and the moment a partial solution can no longer lead to a valid answer, you undo the last choice and try the next option. Think of it as depth-first search over a decision tree: every node is a partial solution, every edge is a choice, and every leaf is either a complete answer or a dead end.
The three verbs that define the pattern:
- Choose — add one option to the current partial solution.
- Explore — recurse deeper with that choice in place.
- Un-choose — remove the option so the next iteration starts clean.
That last step — undoing the choice — is what makes it “backtracking” and is the step candidates most often forget under pressure.
How to Recognize a Backtracking Problem
You are almost certainly looking at backtracking when the problem asks for all solutions rather than one optimal solution. Watch for phrasing like “return all possible…”, “generate every combination…”, or “count the number of valid arrangements”. Other strong signals: the input is small (n ≤ 20 or so, because the search space is exponential), the solution is built incrementally from discrete choices, and constraints can invalidate a partial solution early. If the problem asks for the best solution instead of all of them, first consider dynamic programming or greedy — backtracking is your fallback when no overlapping subproblem structure exists.
The Universal Backtracking Template
Here is the template in Java. Memorize the shape, not the specifics:
void backtrack(State state, List<Choice> choices, List<Result> results) {
if (isComplete(state)) {
results.add(snapshot(state)); // copy! don't add a live reference
return;
}
for (Choice c : validChoices(state, choices)) {
state.apply(c); // choose
backtrack(state, choices, results); // explore
state.undo(c); // un-choose
}
}Two details interviewers deliberately probe: first, you must add a copy of the current path to the results, because the path list keeps mutating as recursion unwinds. Second, the undo must exactly mirror the apply — if you added to a list, remove from the end; if you marked a cell visited, unmark it.
The Five Problems You Must Know
1. Subsets (the gateway problem)
Generate all subsets of a distinct-integer array. The decision at each index is binary — include the element or skip it — producing 2ⁿ leaves. The idiomatic loop version passes a start index so each recursive call only considers elements to the right, which is exactly how you avoid duplicate subsets:
void dfs(int start, int[] nums, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
dfs(i + 1, nums, path, res);
path.remove(path.size() - 1);
}
}2. Permutations
Same skeleton, different choice set: every unused element is a candidate at every position. Track usage with a boolean array. Expect the follow-up “what if the input has duplicates?” — the answer is to sort first, then skip nums[i] when it equals nums[i-1] and the previous copy is unused. That dedup trick recurs across the entire pattern family.
3. Combination Sum
Find combinations that add to a target, with elements reusable. The twist is passing i instead of i + 1 when recursing (allowing reuse) and pruning the loop as soon as the running sum exceeds the target. It tests whether you understand why the start index prevents duplicates rather than just copying it.
4. Word Search (grid backtracking)
Search a 2D board for a word by moving to adjacent cells. This introduces state that lives outside the path: you mark the current cell visited before recursing into its neighbors and restore it after. Forgetting the restore is the single most common bug interviewers see in this problem.
5. N-Queens (constraint propagation)
Place N queens so none attack each other. The elegant insight is representing constraints as three hash sets — columns, main diagonals (row - col), and anti-diagonals (row + col) — so each placement check is O(1). N-Queens is a favorite in senior and tech-lead loops because it rewards clean state modeling, not just recursion mechanics.
Pruning: Where Strong Candidates Separate
Raw backtracking explores the full exponential tree. Pruning cuts branches that provably cannot succeed, and talking about it out loud is what earns “strong hire” signal:
- Feasibility pruning — in Combination Sum, sort the candidates and break out of the loop the moment a candidate overshoots the remaining target; everything after it is larger.
- Symmetry pruning — in N-Queens, the first row only needs to explore half its columns; mirror the results for the other half.
- Constraint-first ordering — try the most constrained choices earliest so contradictions surface high in the tree, where cutting a branch eliminates the most work.
Complexity: What to Say When Asked
Don’t hand-wave “it’s exponential”. Be precise: subsets is O(n · 2ⁿ) — 2ⁿ subsets, each copied in O(n); permutations is O(n · n!); word search is O(m · n · 3ᴸ) since after the first step you never revisit the cell you came from. Space is O(depth) for the recursion stack plus the output. Stating output-sensitive complexity — “the algorithm is optimal because any solution must at least enumerate the output” — is a senior-level answer.
Common Mistakes to Avoid
The four errors that sink otherwise-correct solutions: adding the live path reference to results instead of a copy; forgetting to undo state (especially visited markers in grid problems); mishandling duplicates by deduplicating the output instead of pruning the input; and recursing with the wrong start index, which silently produces permutations when the problem wanted combinations.
A One-Week Practice Plan
Day 1–2: Subsets and Subsets II until you can write the template from memory. Day 3: Permutations I and II, focusing on the duplicate-skipping condition. Day 4: Combination Sum I and II with pruning. Day 5: Word Search and one flood-fill variant. Day 6: N-Queens and Palindrome Partitioning. Day 7: redo the two problems that felt hardest, cold, with a 25-minute timer — that time pressure is what makes the pattern stick for the real interview.
Start Practicing Today
Backtracking looks intimidating until you internalize one template and three verbs: choose, explore, un-choose. Master the five problems above, narrate your pruning decisions in the interview, and this pattern turns from a fear into free points. Block out this week, work the plan, and if you want structured interview preparation to go deeper, check out Niraswa AI. Your next interview is won in the reps you put in now — start today.
