← All patternsBacktracking · template
Pattern · Recursion
Backtracking
Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.
Time Exponential, e.g. O(2^n) or O(n!) · Space O(n) depth plus the output
Taught in Module 13: Backtracking
Think of it like this
Solving a maze with chalk: mark your path, and when you hit a dead end, rub out the marks back to the last junction and try another way.
Clues that point here
- → "Generate all" subsets, permutations or combinations
- → Constraint puzzles (N-Queens, Sudoku)
- → Word search in a grid
- → Small input size (n ≤ 20)
Not this pattern when
- ✕ You only need a count or best value and subproblems overlap (DP)
- ✕ Input is large (exponential time)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
void backtrack(List<Integer> path, int start, List<List<Integer>> out) {
if (isComplete(path)) { out.add(new ArrayList<>(path)); return; }
for (int i = start; i < choices.length; i++) {
if (!allowed(i)) continue; // prune
path.add(choices[i]); // choose
backtrack(path, i + 1, out); // explore
path.remove(path.size() - 1); // unchoose
}
}Common versions
- Subsets
- Permutations
- Combination sum
- Generate parentheses
- N-Queens
- Word search
- Palindrome partitioning
Practice problems with this pattern
13.1SubsetsMediummain pattern13.2Subsets IIMediummain pattern13.3PermutationsMediummain pattern13.4Combination SumMediummain pattern13.5Letter Combinations of a Phone NumberMediummain pattern13.6Generate ParenthesesMediummain pattern13.7Word SearchMediummain pattern13.8Palindrome PartitioningMediummain pattern13.9N-QueensHardmain pattern13.10Sudoku SolverHardmain pattern19.2Design Add and Search WordsMediumalso uses it19.3Word Search IIHardalso uses it22.7All Paths From Source to TargetMediumalso uses it30.2Target SumMediumalso uses it32.8Partition to K Equal Sum SubsetsMediumalso uses it