DFS and backtracking
Depth-first search explores one branch as far as possible before returning to the previous decision point. It is commonly used for reachability, graph traversal, and topological reasoning. A DFS needs a call stack or explicit stack, plus a visited structure when the same node can be reached more than once.
Backtracking is a specialized form of DFS for constraint and enumeration problems such as combinations, permutations, partitions, subsets, and board searches. A normal reachability DFS can return as soon as it reaches its goal; backtracking must undo a choice and continue searching other branches.
Within a single recursive path:
- Mark a choice before the recursive call so it cannot be reused illegally.
- Undo that mark after the call so another branch may use the same value.
Search-tree model
Backtracking problems can be viewed as trees. A for loop enumerates choices horizontally, recursion moves vertically, and the undo step returns to the parent decision.
current path
/ | \
choice A choice B choice C
/ \ / \ / \
next choices in each remaining search spaceThe core template is:
void backtrack(Path path, Choices choices) {
if (isComplete(path)) {
results.add(copyOf(path));
return;
}
for (Choice choice : choices) {
makeChoice(path, choice);
backtrack(path, nextChoices(choices, choice));
undoChoice(path, choice);
}
}Use a startIndex when choosing combinations from one collection. It is unnecessary when choosing once from several independent collections. Permutations do not use startIndex; they use a used array because the same value may appear in different positions across different permutations.
Examples
Combination problems
Combinations — LC 77. Generate every group of k values from 1...n. Continue from i + 1 so a combination is not reordered or repeated.
private void combine(int n, int k, int start, List<Integer> path) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= n; i++) {
path.add(i);
combine(n, k, i + 1, path);
path.remove(path.size() - 1);
}
}Combination Sum — LC 39. Candidates are distinct and may be reused, so recurse with i, not i + 1.
Combination Sum II — LC 40. Each candidate may be used once. Sort first, recurse with i + 1, and skip candidates[i] when it equals the previous value at the same tree level.
Letter Combinations of a Phone Number — LC 17. Each digit provides an independent set of letters, so the recursion advances to the next digit without a startIndex.
Partition problems
Palindrome Partitioning — LC 131. At each index, try every non-empty suffix prefix. Recurse only when the chosen substring is a palindrome.
Restore IP Addresses — LC 93. Build exactly four parts. Each choice contains one to three digits, must be within 0...255, and cannot have a leading zero unless it is exactly "0".
Subset problems
Subsets — LC 78. Every node in the search tree is a valid result, so save the current path before exploring its children.
private void subsets(int[] nums, int start, List<Integer> path) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
subsets(nums, i + 1, path);
path.remove(path.size() - 1);
}
}Subsets II — LC 90. Sort the array and skip equal values at the same tree level with i > start && nums[i] == nums[i - 1].
Permutation problems
Permutations — LC 46. A permutation is ordered, so [1, 2] and [2, 1] are distinct. Iterate the full array at every level and use used[i] to prevent selecting the same position twice in one path.
Permutations II — LC 47. Sort first. In addition to used[i], skip a duplicate when nums[i] == nums[i - 1] and the previous copy has not been used in the current branch.
Board problems
N-Queens — LC 51. Process one row at a time. A queen is valid only when its column and both diagonals are clear; place it, recurse to the next row, then remove it.
Sudoku Solver — LC 37. Find the next empty cell and try digits 1...9. Return immediately when a recursive call completes the board. If no digit fits the current empty cell, return false to backtrack.