Pattern Guide
Backtracking with Pruning
"Prune search space early. Bound functions, symmetry breaking, feasibility checks."
Backtracking explores all possibilities by building candidates incrementally and abandoning (pruning) those that cannot lead to valid solutions. Effective pruning transforms exponential worst-case into practical efficiency. Key pruning strategies: feasibility check (can current partial solution extend to a valid one?), bounding function (can current path beat the best found?), symmetry breaking (avoid redundant symmetric branches), and constraint propagation.
Problems you can solve with this pattern
4 problems · click any to start solving
// Subsets with duplicates — sort + skip duplicates at same level
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [], current = [];
function backtrack(start) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
// Pruning: skip duplicate values at the same recursion level
if (i > start && nums[i] === nums[i-1]) continue;
current.push(nums[i]);
backtrack(i + 1);
current.pop();
}
}
backtrack(0);
return result;
}
// N-Queens — prune by checking column and diagonal conflicts
function solveNQueens(n) {
const result = [], board = Array(n).fill().map(() => Array(n).fill('.'));
const cols = new Set(), diag1 = new Set(), diag2 = new Set();
function backtrack(row) {
if (row === n) { result.push(board.map(r => r.join(''))); return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
cols.add(col); diag1.add(row-col); diag2.add(row+col);
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
}
}
backtrack(0);
return result;
}Backtracking template: choose → explore → unchoose. Pruning: before recursing, check if the partial solution can possibly lead to a valid answer. For optimization: prune if current path cannot beat best answer found so far (branch and bound). For combinatorial: sort first and skip duplicates. For constraint satisfaction: after each assignment, check all constraints are still satisfiable.
// Subsets with duplicates — sort + skip duplicates at same level
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [], current = [];
function backtrack(start) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
// Pruning: skip duplicate values at the same recursion level
if (i > start && nums[i] === nums[i-1]) continue;
current.push(nums[i]);
backtrack(i + 1);
current.pop();
}
}
backtrack(0);
return result;
}
// N-Queens — prune by checking column and diagonal conflicts
function solveNQueens(n) {
const result = [], board = Array(n).fill().map(() => Array(n).fill('.'));
const cols = new Set(), diag1 = new Set(), diag2 = new Set();
function backtrack(row) {
if (row === n) { result.push(board.map(r => r.join(''))); return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
cols.add(col); diag1.add(row-col); diag2.add(row+col);
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
}
}
backtrack(0);
return result;
}- Feasibility: Can current partial solution be extended? (remaining target < min available)
- Bound: Can current path beat best answer? (branch and bound)
- Duplicate skipping: Sort + skip when nums[i] == nums[i-1] at same recursion level
- Constraint propagation: After each choice, check remaining constraints
- Trie pruning: Stop DFS when current prefix matches no word
Key insight for duplicate skipping: The condition is i > start, not i > 0. This allows the same value at different recursion depths but skips duplicates within the same level.