Coding interview pattern
Backtracking
Build candidates incrementally and abandon a partial solution the moment it cannot work.
The idea
How the backtracking pattern works
Backtracking is a refined brute force for problems that ask you to enumerate or find configurations satisfying constraints: all permutations, all subsets, all valid board placements. It builds a candidate one decision at a time, and the instant a partial candidate violates a constraint it prunes that entire branch and backtracks, undoing the last decision before trying the next. The pruning is what separates it from blind exhaustive search.
The canonical structure is a recursive function that takes the current partial solution, tries each available choice, recurses, and then undoes the choice (the explicit backtrack step). Choose, explore, un-choose. Getting the un-choose right is the most common source of bugs: every mutation made before the recursive call must be reverted after it, or state leaks across branches.
Backtracking is inherently exponential because the search space is exponential, so the interview signal is not avoiding that, it is pruning aggressively and structuring the recursion cleanly. Strong candidates identify the earliest possible point to reject a branch (for N-Queens, checking column and diagonal conflicts before placing) so the constant factor stays manageable.
Recognition
When to reach for it
- The problem asks for all valid configurations, or to find one that satisfies constraints.
- You are generating permutations, combinations, subsets, or partitions.
- Choices are made sequentially and a partial choice can be validated early.
- The search space is exponential but heavy pruning is possible.
Cost
Time & space complexity
| Operation | Time | Space |
|---|---|---|
| Subsets | O(2^n) | O(n) recursion |
| Permutations | O(n!) | O(n) recursion |
| N-Queens | O(n!) worst, far less with pruning | O(n) |
Worked example
Walkthrough: Generate all subsets
- 1Recurse with a start index and the current partial subset.
- 2At each call, record the current subset as one valid answer.
- 3For each index from start to the end, choose that element (append it), recurse with the next start index, then un-choose (pop it).
- 4Advancing the start index each level prevents generating the same subset in different orders.
- 5The choose-recurse-unchoose triple is the heartbeat of every backtracking solution.
Translatable skeleton
The shape in pseudocode
Language-agnostic on purpose. Translate it to your language of choice.
def bt(state, start): record(state); for i in range(start, n): choose(i); bt(state, i + 1); unchoose(i)Practice
Curated problem set
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Subsets | Medium | The cleanest introduction to choose/unchoose. |
| Permutations | Medium | Track used elements; n! leaves. |
| Combination Sum | Medium | Reuse allowed; prune when the sum exceeds target. |
| Word Search | Medium | Backtrack over grid cells with visited marks. |
| Palindrome Partitioning | Medium | Cut at every valid palindrome prefix. |
| N-Queens | Hard | Prune on column and diagonal conflicts early. |
Avoid these
Common pitfalls
- Forgetting the un-choose step, so state leaks across branches.
- Recording references to a mutable structure instead of a copy.
- Weak pruning, turning a tractable search into a timeout.
- Generating duplicates when the input has repeated elements.
In the interview
How to communicate it live
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Say the heartbeat aloud, choose, recurse, un-choose, and point out that forgetting the un-choose is the classic bug; verbalising it proves you know the pitfall before you hit it.
Identify the earliest point you can reject a partial candidate and prune there, then explain that aggressive pruning is what keeps an exponential search practical; this is the main signal on backtracking.
When recording an answer, mention that you push a copy of the partial state, not a reference, so later mutations do not corrupt results already collected.
Also searched as
backtracking interview - permutations and combinations - constraint search
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- Backtracking (Chapter 2, Algorithms) Jeff Erickson, University of Illinois Urbana-Champaign
- Competitive Programmer's Handbook: complete search, backtracking and pruning (Chapter 5) Antti Laaksonen, CSES
- Backtracking Wikipedia
Next up
Patterns that pair well with this one
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.