The Mental Model
Backtracking is a DFS search on a decision tree. At every node, you make a choice, explore all resulting possibilities, and then UNDO that choice so you can try the next branch from a clean slate.
1. The Universal Backtracking Template
public void solve() {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), options, 0);
return res;
}
private void backtrack(List<List<Integer>> res, List<Integer> tempPath, int[] options, int start) {
// 1. Base Case: Goal Reached?
if (/* path_is_a_solution */) {
res.add(new ArrayList<>(tempPath)); // Create a deep copy!
return;
}
for (int i = start; i < options.length; i++) {
// 2. Pruning: Is this choice valid?
if (/* condition_to_skip */) continue;
// 3. Choose: Add to path and update state
tempPath.add(options[i]);
// 4. Explore: Recurse to next decision
backtrack(res, tempPath, options, i + 1);
// 5. Un-choose (Backtrack): Undo the choice
tempPath.remove(tempPath.size() - 1);
}
}
2. Key Differences in Patterns
| Requirement | Variation |
|---|---|
| Subsets | No base case check; add every tempPath to res. |
| Permutations | start index is always 0; use a boolean[] used to skip items. |
| Combinations | Use start = i + 1 to avoid using the same item twice. |
3. Interview Discussion: The "Aha!" Moment
When do you use Backtracking? If the problem asks to "Return all possible..." or "Generate all...", backtracking is almost always the answer. If the problem only asks for a count, consider Dynamic Programming instead to avoid redundant branches.