Backtracking
Systematically build and abandon partial solutions to generate subsets, permutations, and combinations - and to solve constraint puzzles like N-queens.
On this page
Backtracking is how you generate all valid possibilities - every subset, every permutation, every arrangement that satisfies some constraints. It's recursion with a twist: you build a partial solution step by step, and when a path can't lead anywhere valid, you undo the last step and try another. The template is remarkably uniform once you see it.
Build, recurse, undo
The backtracking template: at each step, try each available choice, recurse to build on it, then undo the choice before trying the next. That "undo" - restoring state so the next branch starts clean - is what gives backtracking its name:
// generate all subsets of nums
void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current)); // every partial state is a valid subset
for (int i = start; i < nums.length; i++) {
current.add(nums[i]); // choose
backtrack(nums, i + 1, current, result); // explore with this choice
current.remove(current.size() - 1); // un-choose (backtrack)
}
}The three moves - choose, explore, un-choose - are the skeleton of nearly every backtracking solution. What changes between problems is only what a "choice" is and when a partial solution counts.
Permutations and pruning
For permutations, a choice is "which unused element goes next," tracked with a used[] array. The key to
efficiency is pruning: abandoning a branch the moment it can't possibly lead to a valid solution,
instead of exploring it fully:
// all permutations of nums
void permute(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) { result.add(new ArrayList<>(current)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // prune: skip already-used elements
used[i] = true; current.add(nums[i]); // choose
permute(nums, used, current, result); // explore
used[i] = false; current.remove(current.size() - 1); // un-choose
}
}Constraint problems like N-queens or Sudoku are backtracking with heavier pruning: place a queen, check it doesn't conflict, recurse; if a row can't be placed, back out and shift the previous queen. Pruning early is what keeps these from exploring an astronomically large space.
Backtracking is exponential - pruning is survival
Generating all subsets is O(2^n); all permutations is O(n!). These are inherently exponential because the output itself is exponential. You can't beat that when you truly need all possibilities - but aggressive pruning (abandoning dead branches early) is the difference between a solution that finishes and one that runs for hours. Always ask: 'can I detect this branch is doomed sooner?'
To find every path through a maze, you tie a string at the entrance and explore. At each junction you pick a direction and go; if you hit a dead end, you follow the string back to the last junction and try the next unexplored direction, erasing that dead-end branch from consideration. Backtracking is exactly this: 'choose' a direction, 'explore' onward, and when a path dead-ends, 'un-choose' by walking back and trying another. The string is your recursion stack, and pruning is recognizing a corridor is blocked before walking all the way down it.
Generate all combinations of n pairs of well-formed parentheses (e.g. n=2 → "(())", "()()"). Describe the choices at each step and the pruning that keeps you from generating invalid strings.
What are the three core moves of the backtracking template?
Key takeaways
- Backtracking generates all valid possibilities (subsets, permutations, arrangements) via choose, explore, un-choose.
- The 'un-choose' step restores state so each branch starts clean - the essence of backtracking.
- Pruning - abandoning branches that can't lead to a valid solution - is what makes exponential search feasible.
- Subsets are O(2^n) and permutations O(n!): inherently exponential because the output is, so prune aggressively.
- Constraint puzzles (N-queens, Sudoku) are backtracking with heavier validity checks and earlier pruning.