Patterns/Part IV - Core Algorithms/Backtracking with Pruning

Pattern Reference

Backtracking with Pruning

"Constraint propagation, forward checking, branch and bound, sudoku, cryptarithmetic."

Loading...

Deep Dive Tutorial

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.

Backtracking with duplicate pruning and feasibility check
// 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;
}

Worked Problems

1
Sudoku Solver
Hard
Solve ↗
2
Combination Sum II
Medium
Solve ↗
3
Palindrome Partitioning
Medium
Solve ↗
4
Word Search II
Hard
Solve ↗
scissors
Pruning strategies:
- 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.
← All Patterns