Backtracking is the pattern you reach for when a problem asks you to build all valid combinations, permutations, or partitions and there is no clean formula to jump straight to the answer. You construct a candidate step by step, and the moment a partial candidate cannot possibly lead to a valid solution, you undo the last choice and try the next one. Almost every backtracking problem in an interview reduces to the same recursive skeleton: choose, recurse, undo. Learn that skeleton once and problems like Palindrome Partitioning, Remove Invalid Parentheses, and N-Queens stop looking like separate puzzles.
We run mock interviews all day, and backtracking is where we see the widest gap between candidates who have memorized a specific solution and candidates who actually understand the pattern. The first group freezes when the problem is phrased slightly differently. The second group writes the template, fills in three functions, and talks through the pruning. This guide gets you into the second group.
The one template to memorize
Every backtracking solution has the same three moving parts: a base case that records a completed solution, a loop over the next possible choices, and a make-move / recurse / undo-move sandwich. Here it is in Python.
def backtrack(state, path, results):
if is_solution(state, path):
results.append(path.copy()) # record a full solution
return
for choice in candidates(state, path):
if not is_valid(choice, state, path):
continue # prune dead branches early
path.append(choice) # make the move
backtrack(next_state(state, choice), path, results)
path.pop() # undo the move (this is the "back")
Four decisions turn this template into any specific problem:
- What is a complete solution? For Palindrome Partitioning it is reaching the end of the string. For Construct the Lexicographically Largest Valid Sequence it is filling every slot in the array.
- What are the candidates at each step? A digit, a substring, a topping, a board position.
- What makes a candidate valid? This is the pruning check, and it is where most of the runtime savings live.
- What state do you carry down and undo on the way up? An index, a running cost, a set of used values, a partial board.
If you can answer those four questions out loud before writing code, the interviewer already has most of the signal they want.
How to recognize a backtracking problem
Backtracking is a controlled brute force over a tree of choices, so the tells are in the problem statement. Watch for these:
- The prompt says "return all" or "find every" combination, subset, partition, or arrangement. Palindrome Partitioning asking for all valid partitions is the textbook case.
- The prompt asks for the number of distinct ways to split or arrange something, like Split a String Into the Max Number of Unique Substrings.
- The input is small. Constraints like n <= 15 or a string length under 20 are a strong hint that an exponential search is intended. Maximum Path Quality of a Graph, with at most 10 seconds of travel time on tiny graphs, is designed for exhaustive path exploration.
- You need to satisfy a constraint while enumerating, such as removing the minimum number of parentheses in Remove Invalid Parentheses or hitting an exact target in Closest Dessert Cost.
Backtracking overlaps heavily with depth-first search, and the line matters in interviews. DFS explores a fixed graph or tree that already exists. Backtracking builds the search tree implicitly as it goes and prunes branches that violate constraints. When the "nodes" are partial solutions you are assembling, it is backtracking.
Worked example: Palindrome Partitioning
Given a string like "aab", return every way to cut it so each piece is a palindrome. Map it to the template:
- Solution: the cut index reaches the end of the string.
- Candidates: every prefix
s[start:end]starting at the current position. - Valid: that prefix is a palindrome.
- State to undo: the current piece pushed onto the path.
def partition(s):
results, path = [], []
def backtrack(start):
if start == len(s):
results.append(path.copy())
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if piece == piece[::-1]: # prune non-palindromes
path.append(piece)
backtrack(end)
path.pop()
backtrack(0)
return results
For "aab" this yields [["a","a","b"], ["aa","b"]]. Notice the palindrome check is the only pruning; everything else is the raw template. That is the pattern we want you to internalize: the structure is fixed, and the problem-specific logic lives in one if.
Pruning is where interviews are won
A naive backtracker that only checks validity at the leaves is still correct, but it can be orders of magnitude slower and it signals that you do not really understand the search. Strong candidates prune early and prune hard.
Three pruning techniques cover most problems:
-
Reject invalid partial states immediately. In N-Queens you check column and diagonal conflicts before recursing, not after placing all queens. One characteristic of backtracking is that it uses arrays or other data structures to store traversal information, thereby skipping illegal paths. Tracking occupied columns and diagonals in sets turns the validity check into O(1).
-
Deduplicate choices at each level. Remove Invalid Parentheses must return only unique strings, so you skip a choice if it repeats a sibling already tried at the same depth. Sorting the input first, then skipping
choice[i] == choice[i-1]within a loop, is the standard move and it prevents whole duplicate subtrees. -
Bound the search with the best answer so far. In Closest Dessert Cost or Tiling a Rectangle with the Fewest Squares, abandon any branch whose partial cost already exceeds your current best. This branch-and-bound cut is what keeps Stickers to Spell Word tractable: you stop stacking stickers the moment the partial word count cannot beat the minimum you have found.
When a backtracking solution overlaps a subproblem repeatedly (Stickers to Spell Word is a good example, since the same remaining-letters state recurs), add memoization on the state. That is the bridge from backtracking to dynamic programming, and mentioning it unprompted reads as senior.
Complexity: expect exponential, then explain the pruning
Interviewers will ask for the time complexity, and "exponential" alone is not enough. Know the two anchors:
| Problem shape | Rough worst case |
|---|---|
| Generate all subsets | O(2^n) |
| Generate all permutations | O(n!) |
| Partition a string | O(2^n) partitions, each up to O(n) to build |
| N-Queens | O(n!) |
The N-Queens bound is the one candidates get asked to justify most. The time complexity is O(n!) because you try placing a queen in every row recursively, pruning invalid positions. The intuition: the first queen has N placements, the second must avoid the first's column and diagonals so it has fewer, and so on, giving O(N!). Say the worst case, then immediately add that pruning removes most of the tree in practice so the real number of nodes visited is far smaller. That two-part answer is what a good rubric rewards.
The honest framing to give an interviewer: backtracking is brute force with a brain. The upper bound is exponential, but effective pruning is what separates a solution that passes from one that times out.
Practice problems worth your time
If you want to drill the pattern, order matters. Start with pure enumeration, then add constraints, then add optimization. These are all in our backtracking question bank, roughly easiest to hardest:
- Palindrome Partitioning and Split a String Into the Max Number of Unique Substrings: clean introductions to the choose/recurse/undo loop.
- Closest Dessert Cost and Construct the Lexicographically Largest Valid Sequence: add a target constraint and ordering logic.
- Remove Invalid Parentheses: forces deduplication and a minimum-removal bound.
- Stickers to Spell Word and Tiling a Rectangle with the Fewest Squares: reward memoization and branch-and-bound.
- Maximum Path Quality of a Graph: backtracking over an explicit graph under a time budget, blending DFS with state undoing.
Practicing these against an interviewer who asks you to explain the pruning out loud beats grinding them silently. You can run these as timed mock interviews with AI feedback to catch the explanation gaps that a plain code editor never surfaces.
FAQ
Is backtracking the same as DFS?
They share machinery but not intent. DFS traverses a graph or tree that already exists. Backtracking builds the search tree of partial candidates on the fly and abandons branches that violate constraints. Every backtracking algorithm uses DFS-style recursion, but not every DFS is backtracking.
When should I add memoization to a backtracking solution?
When the same state recurs across different branches. If two different sequences of choices land on an identical remaining subproblem (like the same set of unspelled letters in Stickers to Spell Word), cache the result on that state. If states never repeat, as in most permutation problems, memoization adds overhead without benefit.
How do I avoid returning duplicate results?
Sort the candidates and skip a choice when it equals the previous sibling at the same recursion depth, or track used values in a set per level. This removes entire duplicate subtrees rather than filtering duplicates at the end, which is both faster and cleaner to explain.
What complexity should I quote for backtracking questions?
State the worst case honestly (often O(2^n) for subsets or O(n!) for permutations and N-Queens), then note that pruning cuts the practical node count sharply. Interviewers want the upper bound plus the reasoning about why real runs are faster.