✂️

Combinations + Pruning — Cut Dead Branches Early

Sort candidates first, then at each step: if candidates[i] > remain, break (not continue) — no subsequent elements can work either. Pruning reduces O(2ⁿ) to practical time.

✂️ Prune on Excess 📋 Collect at Zero 🔁 Allow Reuse (Comb Sum) Time O(2^t) pruned Space O(t/min)

📋 When to Use

Find all combinations summing to a target
Sort candidates first to enable pruning (break when candidate > remain)
Combination Sum: same candidate allowed multiple times → recurse with i not i+1
Combinations (#77): choose k from [1..n], no reuse → recurse with i+1
N-Queens / Sudoku: constraint propagation is the "pruning" mechanism

💡 break vs continue: Because candidates are sorted, if candidates[i] > remain, all subsequent candidates are also > remain. Use break to stop the entire loop — not continue to skip one element.

⚡ Complexity

Without Pruning

O(2ⁿ)

Depth

O(t/min)

Without pruning: O(2ⁿ) states explored.
With sorting + pruning: dramatically reduced — O(2^(target/min_candidate)) in worst case.
Space: O(target / min_candidate) recursion depth — the max path length before we either hit the target or prune.
Pruning is what makes backtracking practical.

✂️ The Critical Distinction: break vs continue

When candidates are sorted ascending and candidates[i] > remain: use break — not continue. Since the array is sorted, every element after index i is also > remain. Continuing would just check elements that are guaranteed to be too large. break exits the entire loop immediately, pruning all remaining candidates in one shot. This is the heart of the optimization.

🎬 Animation — Combination Sum: candidates=[2,3,6,7], target=7

Problem Given candidates = [2,3,6,7] and target = 7, find all combinations that sum to the target (elements can be reused). Sort first, then at each level try candidates[i..end] passing start=i to allow reuse. Prune entire subtree when candidates[i] exceeds remaining sum.
Input: candidates = [2,3,6,7], target = 7 · Answer: [2,2,3] and [7]

Step 0 / 14

⚙️ Init ➕ Choose ✅ Found! ↩ Backtrack ✂️ Pruned 🎉 Done

Start: Sort candidates, then call bt(start=0, remain=7, curr=[]).

Arrays.sort(candidates);

Recursion Tree

Active

Found!

Pruned ✂️

Visited

Pruned edge

Call Stack

← top (current)

empty

Candidates

2 ✂️

3 ✂️

6 ✂️

7 ✂️

candidates[0]=2 > remain=1 → BREAK!

curr path

[ ]

remain

Results

[ ]

Implementation Java 8

// ─── Combination Sum (candidates can repeat) ─────────────────────
class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);          // ← sort enables pruning
        this.candidates = candidates;
        backtrack(0, target, new ArrayList<>());
        return result;
    }

    void backtrack(int start, int remain, List<Integer> curr) {
        if (remain == 0) {
            result.add(new ArrayList<>(curr));   // exact match — collect
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) break;  // ✂️ PRUNE — sorted, so all next are also > remain
            curr.add(candidates[i]);
            backtrack(i, remain - candidates[i], curr);  // reuse: pass i (not i+1)
            curr.remove(curr.size() - 1);              // backtrack
        }
    }
}

// ─── Combinations #77 (choose k from 1..n, no reuse) ────────────
class Solution77 {
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtrack(1, n, k, new ArrayList<>());
        return result;
    }

    void backtrack(int start, int n, int k, List<Integer> curr) {
        if (curr.size() == k) {
            result.add(new ArrayList<>(curr));
            return;
        }
        // Pruning: need (k - curr.size()) more elements, must be ≤ n - i + 1
        for (int i = start; i <= n - (k - curr.size()) + 1; i++) {
            curr.add(i);
            backtrack(i + 1, n, k, curr);  // i+1: no reuse
            curr.remove(curr.size() - 1);
        }
    }
}

🎯 Practice Problems

#39 Combination Sum sort + prune + reuse i Medium #40 Combination Sum II no reuse + skip duplicates Medium #77 Combinations choose k from [1..n], i+1 Medium #216 Combination Sum III choose k digits summing to n Medium #51 N-Queens pruning via row/col/diag constraints Hard #37 Sudoku Solver constraint propagation as pruning Hard