"Decision tree exploration, pruning, permutations, combinations, subsets, N-queens."
Loading...
Deep Dive Tutorial
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
Universal backtracking 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;
triangle-alert
Always push a copy: 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.
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();
}
};
Backtracking pruning cheat sheet: - 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)