Pruning Techniques

Backtracking explores a decision tree; pruning cuts branches that cannot lead to a valid or optimal solution. This lesson covers constraint, feasibility, bound, and duplicate pruning, the start-index trick for combinations, and implementations in C, Java, and Python with trace tables.

Overview

Naive backtracking tries every path in the state space tree. Pruning returns early when a partial solution violates rules or cannot be extended to a full solution—often reducing exponential work to something manageable.

Search tree without pruning: explore ALL children
Search tree with pruning:  skip subtrees marked ✗

              []
           /  |  \
         [1] [2] [3]
        / \    |    \
    [1,2] [1,3] [2,3]  ...
      ✓     ✓     ✓

Start-index pruning: from [1], only extend with 2,3 — never revisit 1

What is Pruning?

Pruning means stopping exploration of a branch before reaching its leaves because:

• The partial state already violates a constraint, or
• Remaining choices cannot complete a valid solution, or
• Current cost already exceeds the best known solution (optimization).

In code, pruning is usually an early return or continue inside the recursive loop—before or instead of deeper recursion.

Types of Pruning

Constraint Pruning

Check validity before recursing. If the choice is illegal, skip it immediately.

N-Queens example: Before placing a queen at (row, col), verify no queen in same column or diagonal.

Row 1: try col 0,1,2,3
  col 0 conflicts with row 0 → prune (no recurse)
  col 2 valid → recurse to row 2

Same idea in Sudoku: reject digit if row/column/box already contains it.

Feasibility Pruning

Even if the current state is valid, stop if the remaining resources cannot satisfy the goal.

Combinations C(n, k): If len(path) + (n - start) < k, not enough elements left—return without looping.

Combination Sum: If remaining < 0 after picking a candidate, prune (when only positive candidates allowed).

Duplicate & Start-Index Pruning

For combinations (not permutations), use a start index and only pick from start … n-1. Recurse with i + 1—never pick earlier indices again.

For sorted arrays with duplicates (Combination Sum II), skip identical values at the same recursion level:

if i > start and candidates[i] == candidates[i - 1]:
    continue  # duplicate pruning at same depth

Bound Pruning

In optimization problems, keep the best solution so far. If the partial cost plus a lower bound on remaining cost cannot beat the best, prune the branch (branch-and-bound).

Classic interview backtracking often uses constraint + feasibility only; bound pruning appears in OR and advanced search.

Code (C, Java, Python)

Python — Combinations with start-index + feasibility prune

def combine(nums, k):
    """C(n,k) — start-index avoids duplicates; feasibility prune."""
    n = len(nums)
    path, result = [], []

    def backtrack(start):
        # feasibility: not enough elements left to reach k
        if len(path) + (n - start) < k:
            return
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n):
            path.append(nums[i])
            backtrack(i + 1)  # start-index prune
            path.pop()

    backtrack(0)
    return result


if __name__ == "__main__":
    print(combine([1, 2, 3], 2))  # [[1,2], [1,3], [2,3]]

Java — Constraint check (N-Queens style)

public class PruningExample {

    /** Constraint pruning: reject column if attacked. */
    static boolean isSafe(int[] cols, int row, int col) {
        for (int r = 0; r < row; r++) {
            if (cols[r] == col) return false;
            if (Math.abs(cols[r] - col) == row - r) return false;
        }
        return true;
    }

    static void nQueens(int n, int row, int[] cols, int[] count) {
        if (row == n) { count[0]++; return; }
        for (int col = 0; col < n; col++) {
            if (!isSafe(cols, row, col)) continue;  // constraint prune
            cols[row] = col;
            nQueens(n, row + 1, cols, count);
        }
    }

    public static void main(String[] args) {
        int[] count = {0};
        nQueens(4, 0, new int[4], count);
        System.out.println(count[0]); // 2
    }
}

C — Combination sum with remaining prune

#include <stdio.h>

void combo_sum(int *candidates, int n, int target, int start,
               int path[], int depth, int *count) {
    if (target == 0) { (*count)++; return; }
    if (target < 0) return;  /* feasibility prune */

    for (int i = start; i < n; i++) {
        path[depth] = candidates[i];
        combo_sum(candidates, n, target - candidates[i], i,
                  path, depth + 1, count);
    }
}

int main(void) {
    int nums[] = {2, 3, 6, 7};
    int path[16], count = 0;
    combo_sum(nums, 4, 7, 0, path, 0, &count);
    printf("solutions with unlimited reuse: %d\n", count); /* 2 */
    return 0;
}

Output & Trace

Combinations — nums=[1,2,3], k=2

Result: [[1,2], [1,3], [2,3]] — 3 combinations without duplicate orderings.

N-Queens n=4 — constraint pruning effect

Mapping to Track Problems

With vs Without Pruning

Real-Life Applications

Interview Tips

1. Name the pruning type you use (constraint, feasibility, duplicate).
2. For combinations, always mention start index — interviewers expect it.
3. Place cheap checks first (bounds, length) before expensive ones (deep board scans).
4. Draw a small tree and mark pruned branches — shows you understand search space.
5. If states repeat, mention memoization — hybrid of backtracking and DP.
6. Link to backtracking intro and upcoming N-Queens tutorial.