Backtracking builds a solution incrementally, one choice at a time, and abandons, or backtracks out of, a partial solution the moment it becomes clear it cannot possibly lead anywhere valid. It is really just depth-first search over a tree of choices, with one addition: pruning. Instead of exploring every complete combination and checking it at the end, backtracking checks constraints as it goes and cuts off entire branches early, which is what makes it tractable for problems where brute force would take longer than the universe has existed.
What changed in 2026
- The technique itself is unchanged — backtracking has been the standard approach to constraint satisfaction since the 1950s — but constraint solvers built on backtracking, such as SAT and SMT solvers, keep getting faster pruning heuristics, extending what is practically solvable.
- Backtracking remains a heavily tested interview category, specifically because it forces explicit reasoning about state, choice, and undoing a choice cleanly — skills that transfer directly to real recursive code.
- AI-assisted code generation made textbook backtracking templates, like N-Queens, Sudoku, and permutations, easy to produce, shifting the actual skill test toward adapting the template to novel constraints, not reproducing it from memory.
The pattern
Every backtracking solution follows the same shape:
backtrack(partial_solution):
if partial_solution is complete:
record it (or return it)
return
for each candidate choice:
if choice is valid given partial_solution:
make the choice (add to partial_solution)
backtrack(partial_solution) # recurse deeper
undo the choice (remove from partial_solution)
The undo step is what distinguishes backtracking from plain DFS over a tree that already exists — here, the tree of choices is generated on the fly, and reverting a choice before trying the next sibling keeps the search space bounded to actual possibilities.
Worked example: N-Queens
Place n queens on an n-by-n board so none attack each other. Backtracking places queens row by row: for each row, try each column, check whether it conflicts with any queen already placed, same column or same diagonal, and only recurse into the next row if it does not. The moment a placement conflicts, that branch is abandoned immediately — no need to place the remaining queens just to discover the conflict later.
place queen in row 0, col 0 -> valid, recurse to row 1
place queen in row 1, col 0 -> conflict (same column) -> try col 1
place queen in row 1, col 1 -> conflict (diagonal) -> try col 2
place queen in row 1, col 2 -> valid, recurse to row 2
...continues, backtracking out of any row with no valid column
Backtracking vs the alternatives
| Approach |
Explores |
Prunes early |
Typical use |
| Brute force |
Every complete combination |
No |
Only viable for tiny inputs |
| Backtracking |
Partial solutions, abandoned early |
Yes |
Constraint satisfaction, combinatorial search |
| Dynamic programming |
Subproblems, cached |
Not applicable, reuses instead |
Optimization with overlapping subproblems |
| Greedy |
One path, no exploration |
Not applicable, never explores alternatives |
Problems with the greedy choice property |
Where backtracking actually gets used
- Constraint satisfaction puzzles — N-Queens, Sudoku, crossword filling — anywhere a full assignment must satisfy a set of constraints.
- Generating combinations, permutations, and subsets exhaustively, where every valid arrangement is genuinely needed, not just an optimal count.
- Parsing and pathfinding in mazes, trying a direction and retreating when it dead-ends.
- SAT and constraint solvers, which are industrial-strength backtracking with heavily optimized pruning and heuristics for choosing which variable to try next.
Common pitfalls
Forgetting the undo step. Skipping it leaves stale state in the partial solution when trying the next candidate, producing wrong results that are hard to debug because the bug only appears several levels deep in the recursion.
Not pruning early enough. Checking validity only once a solution is complete throws away backtracking entire advantage — the constraint check needs to happen as early as each partial choice allows.
Reaching for backtracking when DP applies. When only an optimal value or count is needed, not every valid arrangement, and subproblems overlap, dynamic programming is dramatically faster than exploring and abandoning full paths.
FAQ
Is backtracking the same as depth-first search?
Backtracking is DFS over an implicitly generated tree of choices, with explicit pruning and an undo step. Every backtracking algorithm is a form of DFS; not every DFS is doing backtracking.
What is the time complexity of backtracking?
Worst case is exponential, the same as brute force, because pruning only helps on average and on specific inputs, not in the guaranteed worst case. Good pruning is what makes the average case tractable.
When should backtracking be used instead of dynamic programming?
When every valid solution is needed, or the actual arrangement rather than just an optimal value, or when subproblems do not overlap enough to make caching worthwhile.
Where to go next