Blog 9: Optimization with Pruning in Backtracking ✂️

Backtracking by itself explores the entire solution space, which can be exponential. But in many problems, we don’t need to explore every path.
That’s where pruning comes in — cutting off branches of the decision tree that can’t possibly lead to an optimal (or valid) solution.

This idea is also known as Branch & Bound in optimization problems.

🔹 Why Pruning Matters?

• Without pruning → exponential time.
• With pruning → we can reduce the search space drastically.
• Pruning avoids wasted exploration of invalid or suboptimal branches.

🔹 Types of Pruning

1. Constraint-based pruning – Stop exploring if current state is invalid.
2. Bound-based pruning – Stop exploring if best possible result from this branch is worse than the current best.
3. Early stopping – Return as soon as a solution is found (for decision problems like “does a path exist?”).

🔹 Problem 1: Knapsack (Branch & Bound)

Maximize profit by selecting items with weight constraints.

At each step:

• Include or exclude an item.
• Bound check: If total weight > capacity, prune branch.

Java Code

public class Knapsack { private static int maxProfit = 0; public static int knapSack(int[] weights, int[] values, int capacity) { backtrack(0, 0, 0, weights, values, capacity); return maxProfit; } private static void backtrack(int index, int currWeight, int currValue, int[] weights, int[] values, int capacity) { if (currWeight > capacity) return; // prune maxProfit = Math.max(maxProfit, currValue); if (index == weights.length) return; // include item backtrack(index + 1, currWeight + weights[index], currValue + values[index], weights, values, capacity); // exclude item backtrack(index + 1, currWeight, currValue, weights, values, capacity); } public static void main(String[] args) { int[] weights = {2, 3, 4}; int[] values = {4, 5, 6}; System.out.println(knapSack(weights, values, 5)); // Output: 9 } } 

🔹 Problem 2: Word Search (LeetCode 79) with Early Pruning

Find if a word exists in a board by moving up/down/left/right.

Pruning: stop as soon as the character doesn’t match.

public class WordSearch { public boolean exist(char[][] board, String word) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (dfs(board, word, i, j, 0)) return true; } } return false; } private boolean dfs(char[][] board, String word, int i, int j, int idx) { if (idx == word.length()) return true; if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return false; if (board[i][j] != word.charAt(idx)) return false; // prune mismatch char temp = board[i][j]; board[i][j] = '#'; // mark visited boolean found = dfs(board, word, i + 1, j, idx + 1) || dfs(board, word, i - 1, j, idx + 1) || dfs(board, word, i, j + 1, idx + 1) || dfs(board, word, i, j - 1, idx + 1); board[i][j] = temp; // unmark return found; } } 

🔹 Problem 3: N-Queens with Pruning

In Blog 5 we solved N-Queens with full backtracking. But with pruning:

• Stop if placing a queen is invalid (row/col/diagonal conflict).
• Maintain cols, diag1, diag2 sets instead of checking every row each time.

This improves from O(N! full search) to much faster.

🔹 Problem 4: Sudoku Solver

Pruning is critical:

• Stop exploring invalid placements early.
• Use constraint propagation (pre-check row, col, subgrid).

🔹 More Problems Where Pruning Helps

• Max Score Path in Grid – prune paths with score < current best.
• Traveling Salesman (TSP) – bound on partial cost.
• Partition Problems (Equal Subset, Palindrome Partitioning).
• Graph Coloring – stop when adjacent nodes conflict.

🔹 Key Takeaways

✅ Always think: Can I detect invalidity early?
✅ Track best-so-far → prune worse candidates.
✅ Constraint pruning + bound pruning = exponential → polynomial improvements in practice.