Algorithms from zero
Backtracking
Imagine you are packing a backpack. You have five items, each with a weight and value. You want to fit the valuable ones while staying under the weight limit. You try putting item 1 in the backpack—then item 2, then item 3. Suddenly the weight exceeds the limit. Instead of trying every remaining item (which is pointless), you take item 3 out and try a different approach. You backtrack. This is the core idea of backtracking: explore choices systematically, and the moment a partial solution cannot possibly lead to a valid answer, abandon that entire branch.
After this lesson you understand backtracking as a template: a systematic depth-first walk of all candidate solutions. You can code the choose-explore-undo pattern in a recursive function. You understand pruning: how to detect when a partial solution is doomed and skip an entire subtree. You see that backtracking solves the same problems brute force does, but faster—sometimes dramatically faster—because pruning cuts away fruitless branches.
What is backtracking?
Backtracking is a recursive technique that explores all candidate solutions by building them incrementally. At each step, you:
- Choose — make a choice (pick an item, place a queen, choose a digit).
- Explore — recurse with that choice, building toward a complete solution.
- Undo — remove the choice and try the next one.
The key phrase is choose, explore, undo. You go deep (recursion), discover a branch is fruitless (no valid solution), then backtrack (undo) and try another branch. Backtracking is a depth-first traversal of the tree of all possible partial solutions.
Partial solutions and constraints
A partial solution is an incomplete answer—you have decided part of the answer (say, the first three items in the backpack) but not all of it. A constraint is a rule the final solution must satisfy (total weight ≤ limit, no two queens attack each other, etc.).
Pruning: the power of backtracking
Without pruning, backtracking explores every possibility—brute force. But backtracking adds a critical feature: pruning. Before recursing, check if the current partial solution already violates a constraint. If it does, you know no descendant of this partial solution can be valid. So you skip the entire subtree. This is the win: you avoid exploring branches that cannot possibly lead to a solution.
Example: Generate all binary strings of length n
A binary string of length 3 is a sequence of three 0s and 1s: 000, 001, 010, 011, 100, 101, 110, 111. There are 2^n possibilities.
Backtracking approach:
- At each position (0 to n-1), choose either 0 or 1.
- After choosing, recurse to the next position.
- Once the string is full (length n), record it.
- Undo the choice and try the other digit.
This explores the full tree (all 2^n possibilities), but the code is clean: one recursive function that tries both choices at each position.
Example: Place queens with pruning
On an n×n chessboard, place n queens so no two attack each other. Brute force: try all C(n², n) placements (combinations of n cells from n² cells). For n=8, that is C(64, 8) ≈ 4 billion—infeasible.
Backtracking with pruning: place queens row by row. For each row, try each column. Before recursing to the next row, check: does the new queen attack any already-placed queen? If yes, prune (do not recurse). If no, recurse.
On row 1, you place a queen in column 1. On row 2, you try column 1 (conflicts with row 1, column 1 — prune). You try column 2 (no conflict — recurse). On row 3, you try columns, pruning as you go. Many branches are pruned early, avoiding a huge search space.
The universal template
function backtrack(partial_solution):
if solution_complete(partial_solution):
record_solution(partial_solution)
return
for each_choice in available_choices:
if is_valid(partial_solution + choice):
make_choice(partial_solution, choice)
backtrack(partial_solution)
undo_choice(partial_solution, choice)The power is in is_valid(). Pruning here decides whether to recurse.
Let us code two backtracking examples: generating binary strings, and a tiny constraint problem.
Example 1: Generate all binary strings of length n
function generateBinaryStrings(n, current = "") {
// Base case: if the string is full, record it
if (current.length === n) {
console.log(current);
return;
}
// Choose 0, explore, undo
generateBinaryStrings(n, current + "0");
// Choose 1, explore, undo
generateBinaryStrings(n, current + "1");
}
generateBinaryStrings(3);
// Output: 000, 001, 010, 011, 100, 101, 110, 111This explores all 2^3 = 8 possibilities. Notice: no pruning here. We are choosing and exploring both branches at each position.
Example 2: Place items in a knapsack with weight limit (with pruning)
Suppose you have items [{weight: 2, value: 3}, {weight: 3, value: 4}, {weight: 1, value: 2}] and a weight limit of 4. Which items do you pack?
function knapsack(items, limit, index = 0, current = [], totalWeight = 0) {
// Base case: explored all items
if (index === items.length) {
console.log("Knapsack:", current, "Total weight:", totalWeight);
return;
}
const item = items[index];
// Choice 1: Include the current item (if it fits)
if (totalWeight + item.weight <= limit) {
current.push(item);
knapsack(items, limit, index + 1, current, totalWeight + item.weight);
current.pop(); // Undo
}
// Choice 2: Skip the current item
knapsack(items, limit, index + 1, current, totalWeight);
}
const items = [
{weight: 2, value: 3},
{weight: 3, value: 4},
{weight: 1, value: 2}
];
knapsack(items, 4);
// Outputs: all valid knapsacks with weight <= 4Notice the check if (totalWeight + item.weight <= limit). This is pruning: if adding the item exceeds the limit, we skip that branch entirely.
Try both examples:
Let us trace the execution of generateBinaryStrings(2) to see the choose-explore-undo pattern.
1
function generateBinaryStrings(n, current = "") {
2
if (current.length === n) {
3
console.log(current); return;
4
}
5
generateBinaryStrings(n, current + "0");
6
generateBinaryStrings(n, current + "1");
7
}
The pattern: choose (0 or 1), go deep, explore completely, come back, choose the other option, go deep again. That is backtracking.
Time complexity depends on pruning.
Without pruning: You explore the entire tree of choices. If there are c choices at each level and the depth is d, the number of nodes is c^d. Each node does O(1) work, so time is O(c^d).
Example: generating all binary strings of length n. Choices at each level = 2 (0 or 1). Depth = n. Time = O(2^n). You generate 2^n strings, so this is optimal (you must touch every string).
With pruning: You skip entire subtrees. The time is harder to analyze, but in the best case, pruning cuts the search space dramatically. In the worst case (no pruning happens), it is still O(c^d).
Example: N-Queens. Brute force (place n queens in n² cells) is O(C(n², n)) ≈ O((n²)!/(n! × (n² - n)!)), which is huge. With pruning, the search space shrinks because you skip branches where queens attack each other. For n=8, pruning cuts it from billions of placements to just 92 solutions (a tiny fraction).
Space complexity: The call stack depth is the depth of recursion, which is d. So space is O(d). The current partial solution takes O(d) or O(d × c) space depending on how you store it.
Why backtracking is powerful: Without pruning, it is brute force (slow, maybe infeasible). With pruning, it is often practical because it avoids exploring branches that cannot work.
How many times is the base case reached when you call generateBinaryStrings(3)?
In the knapsack backtracking function, what does the check `if (totalWeight + item.weight <= limit)` accomplish?
Backtracking is essentially a ___ traversal of the tree of all partial solutions.
Why is pruning important in backtracking?
Common mistake
Mistake: Forgetting to undo the choice. You choose to include an item in the knapsack. You recurse. But you forget to pop the item when you return. Now the item is still in the knapsack for the next branch (when you skip it). This corrupts subsequent partial solutions.
// WRONG
for item in items:
current.push(item);
backtrack(items, current, ...);
// BUG: forgot to pop!
// CORRECT
for item in items:
current.push(item);
backtrack(items, current, ...);
current.pop(); // UndoThe undo step is not optional—it is critical. The partial solution must be clean before you try the next choice.
You write a backtracking function to place 4 items on a shelf. At each step, you choose whether to place the item or skip it. How many leaf nodes (complete solutions) are in the recursion tree?
Backtracking is a recursive technique that explores all candidate solutions by building them step by step.
Choose, explore, undo: At each step, you make a choice, recurse (explore deeper), then undo the choice and try the next one. This is a depth-first walk of the tree of all partial solutions.
Partial solution: An incomplete answer. A constraint is a rule it must satisfy.
Pruning: Before recursing, check if the current partial solution already violates a constraint. If it does, skip the entire subtree (do not recurse). This is the win: you avoid exploring doomed branches.
Time complexity: Without pruning, you explore c^d nodes (c choices per level, d levels). With pruning, you skip many subtrees. In the best case, pruning cuts the search space dramatically. In the worst case (little pruning), it is still exponential.
Template:
function backtrack(partial):
if complete(partial):
record(partial); return
for each choice:
if valid(partial + choice):
add(partial, choice)
backtrack(partial)
remove(partial, choice)Backtracking solves the same problems brute force does—but faster, because pruning skips fruitless branches.