Search Pruning

Pruning means cutting off branches of an exhaustive search that cannot lead to a valid or optimal answer. It is the main way brute force, backtracking, and branch-and-bound stay practical on competitive programming constraints.

Feasibility pruning

Stop exploring as soon as the partial assignment cannot be extended to any valid solution.

• Constraint checks: In N-Queens, isSafe before placing avoids invalid boards.
• Partial sums / resources: If a partial sum already exceeds the target in a subset problem, return.
• Graph / assignment: If a vertex cannot be colored with any available color, backtrack immediately.

void dfs(int depth, /* state */) {
    if (!feasible(state)) return;   // prune infeasible partial solutions
    if (isSolution(state)) { record(); return; }
    for (each choice c) {
        apply(c);
        dfs(depth + 1, state);
        undo(c);
    }
}

Optimality pruning

When you need minimum or maximum cost, keep the best answer so far (best) and skip branches whose lower bound (for minimization) already exceeds best, or whose upper bound cannot beat best for maximization.

• Greedy bound: e.g. remaining items’ optimistic contribution is still worse than best.
• Sorted input: process in an order that makes early termination more likely.

// Minimization sketch: if optimistic_cost(state) >= best, return;

Ordering and heuristics

Pruning fires more often if strong constraints are checked early or choices are ordered so failures appear quickly (e.g. try most constrained variable first in CSP-style search).

Symmetry breaking

Many problems have symmetric solutions (rotations, relabeling). Fix an arbitrary choice for the first few decisions so each equivalence class is explored once (e.g. fix first queen’s column up to symmetry).

Relation to other topics

• Recursive Backtracking — pruning sits inside the recursive search.
• Generating Subsets — recursion + feasibility skips invalid subsets without enumerating all \(2^n\).
• Meet-in-the-middle and bitmask DP — different tradeoffs; pruning reduces DFS cost, meet-in-the-middle changes the search shape.

Complexity

Pruning does not change worst-case exponential behavior in general, but in practice it can reduce the explored nodes from “unusable” to “fits in time.” The effectiveness depends on instance structure and implementation details.

Summary

Idea	Role
Feasibility	Drop partial states that violate constraints
Bounds	Drop partial states that cannot beat the current best
Order / symmetry	Fewer branches, faster failure, fewer duplicates