Chapter 8 · Backtracking¶
Backtracking explores a decision tree while storing only the current path. Each call owns a precise prefix of choices.
Thinking flow · Backtracking or another model?¶
flowchart TD
accTitle: Recognizing backtracking and choosing its decision shape
accDescr: Use backtracking when the task must enumerate or construct choices and a branch can be undone. Use dynamic programming when different histories share the same future state, and BFS when the goal is the fewest legal moves. Within backtracking, choose take-skip for subsets, a start index for combinations, used markers for permutations, and one variable per level for constraint assignment.
A{"What must the search return?"}
A -->|"fewest legal transitions"| B["BFS / shortest path"]
A -->|"best or count, with<br/>repeated future states"| C["Dynamic programming"]
A -->|"one or all valid<br/>constructions"| D{"Can choices form a tree<br/>and be undone?"}
D -->|no| E["Change the state model"]
D -->|yes| F{"What does one level decide?"}
F -->|"take or skip next item"| G["Subset tree"]
F -->|"choose next from suffix"| H["Combination<br/>start index"]
F -->|"choose any unused item"| I["Permutation<br/>used markers"]
F -->|"assign next variable"| J["Constraint search<br/>validity checks"]
G --> K["Add only proved pruning"]
H --> K
I --> K
J --> KThe deciding distinction from DP is state reuse. Backtracking keeps separate histories because their paths or assignments matter; DP merges histories only when their remaining futures are identical.
flowchart TD
accTitle: The choose, recurse, and undo backtracking cycle
accDescr: From the current path, choose a candidate, recurse, undo that choice, and either try another candidate or return.
A["Current path"] --> B["Choose candidate"]
B --> C["Recurse"]
C --> D["Undo choice"]
D --> E{"More candidates?"}
E -->|yes| B
E -->|no| F["Return"]The call cycle above is the mechanism. The explored search space is a tree. For
the choices [1, 2], every level decides whether to take the next value:
flowchart TD
accTitle: Backtracking decision tree for the subsets of one and two
accDescr: Starting with an empty path, the first level takes or skips one and the second level takes or skips two, producing the four leaves one-two, one, two, and empty. Returning from a child undoes that branch's last choice before exploring its sibling.
A["start: path = []"]
A -->|"take 1"| B["path = [1]"]
A -->|"skip 1"| C["path = []"]
B -->|"take 2"| D["emit [1, 2]"]
B -->|"skip 2"| E["emit [1]"]
C -->|"take 2"| F["emit [2]"]
C -->|"skip 2"| G["emit []"]Siblings must begin from the same parent state. That is why the return from a child and the undo operation belong together.
Core invariant¶
path contains exactly the choices made on the current root-to-node branch.
The undo step must restore the state seen before the choice.
Subsets with duplicates¶
Adjacent duplicate skipping has a precondition: candidates must be sorted. Skip a duplicate only when it appears later in the same decision layer.
def unique_subsets(values: Sequence[int]) -> list[list[int]]:
"""Return every distinct subset, including the empty subset."""
# Sorting places equal sibling choices next to one another.
candidates = sorted(values)
answer: list[list[int]] = []
path: list[int] = []
def search(start: int) -> None:
# Every current path is one valid subset.
answer.append(path.copy())
for index in range(start, len(candidates)):
# Skip a duplicate only within this decision layer.
if index > start and candidates[index] == candidates[index - 1]:
continue
# Choose, recurse, then undo before trying the next sibling.
path.append(candidates[index])
search(index + 1)
path.pop()
search(0)
return answer
inline std::vector<std::vector<int>> unique_subsets(
std::vector<int> values) {
// Sorting places equal sibling choices next to one another.
std::sort(values.begin(), values.end());
std::vector<std::vector<int>> answer;
std::vector<int> path;
std::function<void(int)> search = [&](int start) {
// Every current path is one valid subset.
answer.push_back(path);
for (int index = start; index < static_cast<int>(values.size()); ++index) {
if (index > start && values[index] == values[index - 1]) {
continue;
}
// Choose, recurse, then undo before trying the next sibling.
path.push_back(values[index]);
search(index + 1);
path.pop_back();
}
};
search(0);
return answer;
}
inline std::vector<std::vector<int>> unique_subsets(
std::vector<int> values) {
// Sorting places equal sibling choices next to one another.
std::sort(values.begin(), values.end());
std::vector<std::vector<int>> answer;
std::vector<int> path;
std::function<void(int)> search = [&](int start) {
// Every current path is one valid subset.
answer.push_back(path);
for (int index = start; index < static_cast<int>(values.size()); ++index) {
if (index > start && values[index] == values[index - 1]) {
continue;
}
// Choose, recurse, then undo before trying the next sibling.
path.push_back(values[index]);
search(index + 1);
path.pop_back();
}
};
search(0);
return answer;
}
The condition i > start preserves the ability to choose the same value at a
deeper layer while preventing identical sibling branches.
Pruning¶
A prune is valid only when no completion below the current state can beat or satisfy the answer. Common proofs use:
- a capacity already exceeded;
- a lower bound already worse than the best answer;
- remaining values unable to reach a target;
- a constraint violated by every extension.
Avoid changing shared state in the prune condition unless its restoration is obvious.
Complexity¶
State the number of candidate states and the work per emitted answer. For
subsets, there are 2^n outputs and copying each path can make the total
O(n 2^n).
Practice ladder · draw one decision level¶
| Rung | Problem | Thinking prompt |
|---|---|---|
| 1 | Subsets | What binary choice advances one level? |
| 2 | Combination Sum | Does choosing a value keep or advance its index? |
| 3 | Word Search | Which mutation must be undone after the call? |
| 4 | N-Queens | Which conflict sets make pruning constant-time? |
Sketch two levels and label choose → explore → unchoose before coding.