Pattern Guide
Backtracking
"Try every option. Undo. Move on."
Backtracking is systematic brute-force with pruning. One universal template handles permutations, combinations, subsets, N-queens, and Sudoku. The power is in the pruning conditions.
Problems you can solve with this pattern
10 problems · click any to start solving
const result = [];
const backtrack = (start, current) => {
// Base case: is this a valid complete solution?
if (isComplete(current)) {
result.push([...current]); // ALWAYS push a copy, not a reference
return;
}
for (let i = start; i < choices.length; i++) {
// Pruning: skip this choice if it can't lead to valid solution
if (!isValid(current, choices[i])) continue;
current.push(choices[i]); // Choose
backtrack(i + 1, current); // Explore (i+1 to avoid reuse)
// or backtrack(i, current) // if reuse allowed (unbounded)
current.pop(); // Unchoose (backtrack)
}
};
backtrack(0, []);
return result;Backtracking is the most important pattern to understand before trying to "optimize" it. It's brute force exploration of a decision tree where you build a solution incrementally, and when a partial solution can't possibly lead to a valid complete solution, you prune that branch early and backtrack. The universal template is the same for almost every backtracking problem — only the pruning condition and what constitutes a "valid complete solution" changes.
The Universal Template
const result = [];
const backtrack = (start, current) => {
// Base case: is this a valid complete solution?
if (isComplete(current)) {
result.push([...current]); // ALWAYS push a copy, not a reference
return;
}
for (let i = start; i < choices.length; i++) {
// Pruning: skip this choice if it can't lead to valid solution
if (!isValid(current, choices[i])) continue;
current.push(choices[i]); // Choose
backtrack(i + 1, current); // Explore (i+1 to avoid reuse)
// or backtrack(i, current) // if reuse allowed (unbounded)
current.pop(); // Unchoose (backtrack)
}
};
backtrack(0, []);
return result;result.push([...current]) not result.push(current). Since current is mutated throughout, if you push a reference you'll end up with all result entries pointing to the same (empty) array when the recursion completes.The Three Variants
| Problem Type | Loop Start | Avoid Duplicates? |
|---|---|---|
| Permutations (order matters) | Always 0, use used[] or swap | used[] to skip already-chosen indices |
| Combinations (order doesn't matter) | start = i+1 each level | Sort + skip same value at same level |
| Subsets | start = i+1 each level | Sort + skip same at same level for subset II |
Sort first. Skip same value at the same recursion level.
Variation Trick
Same Template, Different Pruning
Base template
const backtrack = (start, current) => {
if (isComplete(current)) { result.push([...current]); return; }
for (let i = start; i < n; i++) {
if (/* PRUNING */ canSkip(i, current)) continue; // ← just change this
current.push(nums[i]);
backtrack(/* NEXT START */, current); // ← and this
current.pop();
}
};Change only one line to solve:
Subsets
Every node in the decision tree is a valid subset
Word Search
Grid backtracking: mark visited, explore 4 directions, unmark on backtrack
Palindrome Partitioning
Same combination template, different validity check
- Combinations: sort first, then
if (i > start && nums[i] === nums[i-1]) continue to skip dups- Permutations with dups: sort first, then
if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue- Combination sum:
if (candidates[i] > remaining) break (sorted input)- N-Queens: 3 sets (col, diag1, diag2) for O(1) conflict check
- Grid DFS: mutate board in place (set to '#') instead of a visited array
- Palindrome partition: precompute isPalin[i][j] DP to make pruning O(1)