Coding interview pattern
Build candidates incrementally and abandon a partial solution the moment it cannot work.
The idea
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
Cost
| 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
Translatable skeleton
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
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
In the interview
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.
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.
Next up
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Solve overlapping subproblems once, store the results, and build the answer up.
See all coding patterns, the coding questions for your role, and the behavioral round.