A Three-Slot Template Turns Every Backtracking Problem into Fill-in-the-Blanks
Don't Write Recursion by Intuition Anymore — Three Pitfalls + One Template, Backtracking No Longer Relies on Guesswork
1. Opening: You've Rewritten This "Permutations" Problem Three Times
LeetCode 46 Permutations. You think to yourself: "Backtracking, right? Just a for loop plus recursion."
// ❌ First version: forgot to undo
function permute(nums) {
const result = [], path = []
function dfs() {
if (path.length === nums.length) {
result.push(path) // ⚠️ Directly pushed the reference
return
}
for (let n of nums) {
if (path.includes(n)) continue
path.push(n)
dfs()
// ⚠️ Forgot pop()! Undo step missing!
}
}
dfs()
return result
}
// After running, result is full of the same empty array [] — because it pushed a reference, and there was no undo
You delete it and rewrite. The second time you add pop(), but forget the used[] marker, so duplicate elements aren't filtered out. The third time you finally get it right, but the interviewer asks "How would you modify it for combinations?" — and you're stuck again.
Root cause: You haven't abstracted backtracking into a template. Every time you write it by intuition, so every time you have to start over. This article condenses backtracking into a single formula — permutations, combinations, subsets, all by changing just three things.
2. Core Concept: Distinguish Recursion and Backtracking Before You Write
Recursion: Breaking a big problem into smaller, similar sub-problems until they are small enough to solve directly. Formula:
f(n) = g(f(n-1)).
Backtracking: Encoding the process of "try → retreat → try another path" into code. Its essence is adding one extra step after the "return" phase of recursion — undoing the choice just made.
Look at pure recursion first, then backtracking — feel the difference:
// Pure recursion: Factorial — only "forward" and "return", no "retreat and switch paths"
function factorial(n) {
if (n <= 1) return 1 // Termination condition
return n * factorial(n - 1) // Sub-problem relationship
}
// Backtracking: Permutations — adds "make a choice" and "undo a choice"
function permute(nums) {
// ... full code in Step 2
path.push(nums[i]) // Make a choice
backtrack() // Recurse
path.pop() // Undo the choice ← The extra step that defines backtracking
}
One-sentence distinction: Pure recursion goes down one path to the end; backtracking goes down one path, records it, retreats to the fork, and takes another path.
3. Core Code
Step 1: The Universal Backtracking Template
function backtrack(path, choiceList) {
if (termination condition met) {
result.push([...path]) // ⚠️ Must copy! Reason below
return
}
for (let choice of choiceList) {
if (choice is invalid) continue // Pruning
path.push(choice) // 🔑 Make a choice
backtrack(path, newChoiceList)
path.pop() // 🔑 Undo the choice — perfectly symmetrical with "make a choice"
}
}
⚠️ result.push([...path]) cannot be written as result.push(path). Because path is a reference, and subsequent pop() operations will modify it — eventually result will be full of the same empty array.
The essence of this pitfall is JavaScript's object reference mechanism. What you push is the address of an array object, not its value. Later, when you pop() and modify that array, the address stored in result points to the same array — which naturally gets modified too. [...path] creates a new array, severing that connection.
Step 2: Permutations (LeetCode 46) — First Template Modification
Given
[1, 2, 3], return all permutations.
function permute(nums) {
const result = []
const path = []
const used = new Array(nums.length).fill(false) // 🔑 Marks which ones have been used
function backtrack() {
if (path.length === nums.length) { // 🔑 Termination condition: all selected
result.push([...path]) // ⚠️ Copy!
return
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue // 🔑 Pruning: skip used ones
path.push(nums[i]) // Make a choice
used[i] = true
backtrack()
path.pop() // Undo the choice (perfectly symmetrical with above)
used[i] = false
}
}
backtrack()
return result
}
Key choice for permutation problems: Need used[] marker, because [1,2] and [2,1] are different permutations. The same number cannot be reused, but can be selected again in different positions.
Decision tree (permute([1,2,3])):
[]
/1 |2 \3
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
Backtracking = depth-first traversal of this tree. Record when reaching a leaf, then retreat one level and take another branch.
Step 3: Combinations (LeetCode 77) — Second Template Modification
Choose k numbers from
[1..n], return all combinations. Note that[1,2]and[2,1]count as the same.
function combine(n, k) {
const result = []
const path = []
function backtrack(start) { // 🔑 One more `start` parameter than permutations
if (path.length === k) {
result.push([...path])
return
}
for (let i = start; i <= n; i++) { // 🔑 Start from `start`, don't look back
path.push(i)
backtrack(i + 1) // 🔑 Next layer starts from i+1
path.pop()
}
}
backtrack(1)
return result
}
Combinations vs Permutations: Only two things changed:
| Modification | Permutations | Combinations |
|---|---|---|
| Loop start | let i = 0 pick from beginning each time |
let i = start only pick forward |
| Recursion parameter | backtrack() no parameter |
backtrack(i + 1) move start forward |
| Deduplication method | used[] array marker |
start parameter ensures no turning back |
🔑 The
startparameter is the core of combination problems: It ensures each number is used only once and never looks back, naturally preventing duplicates like[1,2]and[2,1].
Step 4: Subsets (LeetCode 78) — Third Template Modification
Given
[1, 2, 3], return all subsets (including the empty set).
function subsets(nums) {
const result = []
const path = []
function backtrack(start) {
result.push([...path]) // 🔑 Record at every node! Not just at leaves
for (let i = start; i < nums.length; i++) {
path.push(nums[i])
backtrack(i + 1) // Same as combinations, no turning back
path.pop()
}
}
backtrack(0)
return result
}
The only difference between subsets and combinations: The termination condition.
- Combinations: Record only when
path.length === k(only specific lengths) - Subsets: Record at every step (collect every node on the decision tree, regardless of depth)
Decision tree comparison ([1,2,3]):
Combinations k=2: Subsets:
[] ← skip [] ← record ✅
├1 ├1 ← record ✅
│├2 → [1,2] ✅ │├2 → record ✅
│└3 → [1,3] ✅ │└3 → record ✅
├2 ├2 ← record ✅
│└3 → [2,3] ✅ │└3 → record ✅
└3 ← skip └3 ← record ✅
Same tree. Combinations only pick fruit at a specified depth; subsets pick as they pass by.
Template Summary: The Three Problems Modify the Same Code
// 🔑 Three elements of backtracking — each problem only requires changing these three places
function backtrack(...) {
if (/* 🔴 Change here: When to record the answer? */) {
result.push([...path])
return
}
for (let i = /* 🔴 Change here: Where to start picking? */; i < ...; i++) {
if (/* 🔴 Change here: What situation to skip? */) continue
path.push(...)
backtrack(/* 🔴 Change here: Where does the next layer start? */)
path.pop()
}
}
| Problem Type | Record Condition | Loop Start | Pruning | Next Layer Parameter |
|---|---|---|---|---|
| Permutations | path.length === n |
i = 0 |
used[i] |
No start |
| Combinations | path.length === k |
i = start |
None (or pruning optimization) | i + 1 |
| Subsets | Record on every entry | i = start |
None | i + 1 |
4. Conclusion: Next Time You Face a Backtracking Problem, Copy the Template and Change Three Things
Call back to the opening: You rewrote permutations three times at the start not because you aren't smart — it's because you wrote it by intuition each time, without internalizing "make a choice → recurse → undo a choice" into muscle memory. Next time you encounter a backtracking problem, don't think about the details first. Type out this template first, then modify those three places.
One-Sentence Summary (Screenshot and share)
Backtracking = Recursion + Make a choice + Undo the choice (perfectly symmetrical). Permutations use a used[] marker, combinations use a start parameter to avoid looking back, subsets record as they pass by.
result.push([...path])must be a copy, otherwise it's all for nothing.
Pitfall Checklist
| Pitfall | Symptom | Fix |
|---|---|---|
result.push(path) without copying |
result is full of empty arrays | result.push([...path]) |
| Forgetting the termination condition | Maximum call stack size exceeded |
Write the termination condition on the first line of every recursive function |
| Undo not done cleanly | Results of later branches mixed with remnants from previous ones | Make and undo choices must correspond one-to-one, perfectly symmetrical |
| Duplicate elements not deduplicated | Permutation results have duplicates | Sort, then if (i > start && nums[i] === nums[i-1]) continue |
| Recursion too deep, stack overflow | Error when exceeding roughly 10,000 layers | Switch to iteration or tail recursion |
Next Steps
- Hand-write this template three times until you can type it out without looking.
- Use the template to solve three variants: 39. Combination Sum, 40. Combination Sum II, 47. Permutations II — feel how "the template stays the same, only three things change."
- Try to draw the decision tree for permutations from understanding, without looking at the code — interviewers love asking candidates to draw this.
An open question: How do you calculate the time complexity of backtracking? Permutations are O(n!), combinations are O(C(n,k)), subsets are O(2^n) — where do these numbers come from? Can you explain them using the number of nodes in the decision tree? Discuss in the comments 👇