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.

---