Backtracking
Systematisch Teillösungen bauen und verwerfen, um Teilmengen, Permutationen und Kombinationen zu erzeugen - und Constraint-Rätsel wie N-Damen zu lösen.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
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.