Chapter 19 — Backtracking
Chapter 19 — Backtracking
Hey everyone! Welcome to Season 5 — Advanced Algorithms! The final stretch.
Backtracking is how you explore every possibility in a smart way: make a choice, explore where it leads, and if it doesn't work, undo it and try the next option. It's recursion with a "rewind" button — and it solves subsets, permutations, N-Queens, and Sudoku.
What we will cover:
- Choose → Explore → Un-choose
- The backtracking template
- Subsets
- Permutations
- N-Queens intuition
- Pruning — cutting dead branches
- Interview Questions
1. Choose → Explore → Un-choose
┌─────────────────────────────────────────────────────────────┐ │ THE BACKTRACKING LOOP │ ├─────────────────────────────────────────────────────────────┤ │ for each option: │ │ 1. CHOOSE → add the option to your path │ │ 2. EXPLORE → recurse deeper │ │ 3. UN-CHOOSE → remove it (BACKTRACK), try next │ │ │ │ The "un-choose" step is what makes it backtracking! │ └─────────────────────────────────────────────────────────────┘
2. The Template
function backtrack(path, choices) {
if (isComplete(path)) {
results.push([...path]); // copy! path keeps changing
return;
}
for (const choice of choices) {
if (!isValid(choice)) continue; // pruning
path.push(choice); // CHOOSE
backtrack(path, remaining); // EXPLORE
path.pop(); // UN-CHOOSE
}
}
Critical detail: push a copy ([...path]) to results, because path is mutated as you backtrack.
3. Subsets — All Possible Combinations
function subsets(nums) {
const res = [];
function backtrack(start, path) {
res.push([...path]); // every node is a valid subset
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose
backtrack(i + 1, path); // explore (i+1 → no reuse)
path.pop(); // un-choose
}
}
backtrack(0, []);
return res;
}
DECISION TREE for subsets([1,2,3]):
[ ]
/ | \
[1] [2] [3]
/ \ \
[1,2] [1,3] [2,3]
/
[1,2,3]
Result: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]
That's 2³ = 8 subsets → O(2ⁿ).
4. Permutations — All Orderings
function permutations(nums) {
const res = [];
function backtrack(path, used) {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // skip already-used
used[i] = true; path.push(nums[i]); // choose
backtrack(path, used); // explore
used[i] = false; path.pop(); // un-choose
}
}
backtrack([], []);
return res;
}
// n! permutations → O(n!)
5. N-Queens Intuition
Place N queens on an N×N board so none attack each other. Backtracking: place a queen in a row, check it's safe, recurse to the next row; if stuck, backtrack.
Try row by row: ┌───┬───┬───┬───┐ │ . │ Q │ . │ . │ row 0: place queen, recurse ├───┼───┼───┼───┤ │ . │ . │ . │ Q │ row 1: only safe column ├───┼───┼───┼───┤ │ Q │ . │ . │ . │ row 2 ├───┼───┼───┼───┤ │ . │ . │ Q │ . │ row 3 → solution! ✔ └───┴───┴───┴───┘ If a row has no safe column → backtrack to previous row.
6. Pruning — Cutting Dead Branches
Pruning is the secret to making backtracking fast: abandon a branch the moment it can't possibly lead to a valid answer, instead of exploring it fully.
┌─────────────────────────────────────────────────────────────┐ │ WITHOUT pruning: explore the entire tree (slow) │ │ WITH pruning: skip branches that already violate a │ │ constraint (e.g. queen under attack) │ │ │ │ Same correctness, dramatically fewer nodes visited. │ └─────────────────────────────────────────────────────────────┘
Interview Questions — Quick Fire!
Q: What is backtracking?
"A refined brute force that builds a solution incrementally: you make a choice, recurse to explore its consequences, and if it leads to a dead end you undo the choice and try the next option. The undo step — un-choosing — is what defines backtracking."
Q: Why must you push a copy of the path to your results?
"Because the path array is mutated throughout the recursion — you push and pop as you choose and un-choose. If you stored a reference, all results would end up pointing to the same array, which becomes empty at the end. Spreading it into a new array snapshots the current state."
Q: What's the difference between subsets and permutations?
"Subsets are about which elements to include, order doesn't matter, giving 2ⁿ results — you iterate from a start index so you never reuse earlier elements. Permutations are about ordering all elements, giving n! results — you track which elements are used and can pick any unused one at each step."
Q: What is pruning and why does it matter?
"Pruning means abandoning a branch as soon as it can't yield a valid solution, like skipping a column where a queen would be attacked. It doesn't change correctness but cuts the search space enormously, which is what makes backtracking practical on problems like N-Queens and Sudoku."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Core loop | Choose → Explore → Un-choose. |
| Copy results | Push [...path], not the reference. |
| Subsets | start index, no reuse → 2ⁿ. |
| Permutations | used[] tracker → n!. |
| Pruning | Drop invalid branches early. |
What's Next?
Chapter 20: Greedy Algorithms — make the locally best choice at each step. We'll see when that magically gives the global best... and when it fails.
Keep coding, keep grinding! See you in the next one!
Post a Comment