Backtracking
Backtracking tries every possibility systematically: pick a step, go deeper, and when a constraint is hit, go back and undo the last choice to try another option.
It is the standard way to enumerate all solutions (subsets, permutations, combinations) or to find a valid configuration (N-Queens, Sudoku). The key to keeping it fast is pruning early — dropping choices that cannot possibly lead to a solution.
Like finding your way home to your village — take a wrong alley and you go back to its entrance and try another.
Try every possibility systematically and cut branches early when you hit a constraint: if this alley is already clearly wrong, don't keep going, turn back right away.
How to spot it
When you see these cues in the problem, reach for Backtracking
| Keyword in the problem | Why it points to this topic |
|---|---|
| enumerate combinations | Subsets, permutations, combinations |
| find one valid assignment | N-Queens, Sudoku, Word Search |
| decision tree | Each step branches into several choices |
| prune early | Check constraints before recursing |
When to use
3 typical situations where this topic applies
You need to enumerate every combination, permutation, or subset that satisfies a constraint
"Try everything" problems: N-Queens, Sudoku, Word Search on a grid
The search space can be narrowed with early constraints (pruning)
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
The problem has a closed-form formula or a polynomial DP: using the right approach is far cheaper
You only need to FIND one valid solution (not list them all): greedy / heuristics may be enough
The search space is huge and cannot be pruned: backtracking will TLE — switch approach (DP / greedy)
Illustration
A diagram of how this topic works.
Each node is a state. Going down means taking or skipping one element. At a leaf, record the result, then go back and try another branch.
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function backtrack(state: State, choices: Choice[], result: R[]): void {
// Base case: goal reached, record the result
if (isGoal(state)) {
result.push(clone(state))
return
}
for (const choice of choices) {
// Prune: skip invalid choices early
if (!isValid(choice, state)) continue
// Choose: apply the choice to state
apply(state, choice)
// Recurse: explore with the new state
backtrack(state, nextChoices(state), result)
// Unchoose: roll back (important!)
undo(state, choice)
}
}Recap
A quick summary — reread it before your interview
Key points
Three-step template: choose — recurse — unchoose (choose, recurse, unchoose)
Base case: when you reach a valid result, record it and return
Pruning: check constraints before recursing → cut bad branches early
Backtracking is just DFS with pruning — the difference is where you cut branches
Common mistakes
Forgetting to unchoose after recursing → state gets "polluted" across branches
Wrong pruning condition → skips valid results or fails to cut bad branches
Forgetting to copy when saving a result:
result.push(current)instead ofresult.push([...current])→ every entry points to the same array, and they all end up empty
Complexity
Time O(b^d) — b là branching factor, d là độ sâu; pruning giảm đáng kể trong thực tếPractice problems for this topic
Grouped by difficulty — work through them in order to build confidence