Introduction to Backtracking
Choose, explore, unchoose — build every subset with one recursive call per candidate.
Examples
Eight subsets, one recorded by each of the eight calls.
The root records the empty subset, its one child records [0].
1. What is Backtracking?
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point of time (this is the "backtrack" step).
Think of it as "Smart Brute Force". Instead of blindly generating every possible combination (like a brute force approach might), Backtracking uses pruning to abandon a path as soon as it determines the path cannot lead to a valid solution.
2. The Motivation: Dynamic Choices
Imagine you need every subset of [1, 2, 3].
- Size 0:
[] - Size 1:
[1],[2],[3] - Size 2:
[1,2],[1,3],[2,3] - Size 3:
[1,2,3]
That is 8 subsets, which is 2³ — each number is either in or out, so every number you add doubles the answer.
If the array were always three long you could write three nested for loops. But n is only known at runtime, and you cannot write n nested loops. Recursion is how you get nesting that is as deep as the input, and backtracking is what keeps the bookkeeping straight while you do it.
3. Attempt 1: Iterative Approach (Why it fails)
A common instinct is to use loops. For N=2, it works:
for i in range(n):
for j in range(i+1, n):
print([nums[i], nums[j]])
The Problem: This code is rigid. It can only find subsets of size 2. To find subsets of size 3, you'd need another loop. To find subsets of size N, you'd need N loops. Since N is unknown until runtime, pure iteration fails.
4. Visualizing the Approach
Draw the calls as a tree and the method stops being abstract.
- Root: the call with an empty path.
- A branch: one number being added to the path.
- Every node: a call, holding one partial subset — and in this method, every node records it.
The figure below is exactly that tree. backtrack(0) has one child for each number it may take first; each of those has one child for each number after it. Looking only forwards is what stops [1, 3] and [3, 1] both being produced — the tree has no room for the second.
5. When should I use Backtracking?
Look for these Pattern Triggers:
Find all solutions: "Return all substrings", "Generate all parentheses", "All permutations".
Constraint Satisfaction: "Solve Sudoku", "N-Queens", "Valid word placement".
Combinatorial Optimization: "Knapsack problem" (small constraints).
Valid Arrangements: Subsets, Combinations, Permutations.
6. The Intuition: Choose, Explore, Unchoose
The mantra for Backtracking is:
- Choose: Make a choice (add an element to your current candidate).
- Explore: Recursively move to the next state (call the function again).
- Unchoose (Backtrack): Undo the choice (remove the element) to return to the previous state.
This "Unchoose" step is why it's called Backtracking. It allows you to reuse the same data structure (current_path) for all solutions, saving memory.
7. Interactive Walkthrough
ONE NODE PER CALL · THE LABEL IS THE NUMBER IT ADDED, THE LINE BELOW IS THE SUBSET IT RECORDS
EMPTY RESULT AND PATH
path
[]
subsets found
0
Answer
—
call stack
No call running
result
Nothing recorded yet
Start with an empty result and an empty path. The numbers are 1, 2, 3
Next
backtrack(0): every call records its own path — result gains the empty subset []
nums
Legend & Complexity
The call running now
A call further up that is waiting for this one to return
Returned — its subset is already in the result
The number just chosen or unchosen
Time
O(n × 2ⁿ)
Space
O(n) path, O(n × 2ⁿ) output
Every node is one call to backtrack. Its label is the number that call added, and the line under it is the path that call holds — which is the subset it records the moment it is entered, so the result list beside the figure fills in the order the tree is walked. The number in amber is the one being chosen or unchosen on this step. Step through the Two numbers preset first: four calls, four subsets.
8. Dry Run Table
Tracing [1, 2] all the way through — seven calls and returns, no ellipsis.
| # | Inside | Path | What happens |
|---|---|---|---|
| 1 | backtrack(0) |
[] |
Records []. Chooses 1 → calls backtrack(1) |
| 2 | backtrack(1) |
[1] |
Records [1]. Chooses 2 → calls backtrack(2) |
| 3 | backtrack(2) |
[1,2] |
Records [1,2]. The loop has nothing to try — returns |
| 4 | backtrack(1) |
[1] |
Unchooses 2. Its loop is finished — returns |
| 5 | backtrack(0) |
[] |
Unchooses 1. Chooses 2 → calls backtrack(2) |
| 6 | backtrack(2) |
[2] |
Records [2]. Nothing to try — returns |
| 7 | backtrack(0) |
[] |
Unchooses 2. Its loop is finished — returns |
Result: [[], [1], [1,2], [2]] — four subsets for two numbers, which is 2².
Notice rows 4 and 7: unchoosing is not bookkeeping for its own sake. Without the pop at row 4, row 5 would start from [1, 2] and produce [1, 2, 2].
9. The Solution: Subsets (LeetCode 78)
The template above, filled in for LeetCode 78. Every line of it is one of the five moves: record, choose, explore, unchoose, return.
Introduction to Backtracking Code
1var subsets = function(nums) {2 const result = [];3 const path = [];45 const backtrack = (start) => {6 result.push([...path]);7 for (let i = start; i < nums.length; i++) {8 path.push(nums[i]);9 backtrack(i + 1);10 path.pop();11 }12 };1314 backtrack(0);15 return result;16};
10. Edge Cases & Common Mistakes
Watch out for these pitfalls:
Reference vs Value: Attempting to store
currentlist directly without making a copy (e.g.,res.add(current)in Java). This results in a list of empty arrays becausecurrentis emptied by backtracking.Base Case Logic: Forgetting to return after a base case, causing stack overflow or invalid states.
State Cleanup: Forgetting to
pop()or remove the element after the recursive call. This 'pollutes' the state for future branches.