Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Backtracking & Pruning
DSA

Backtracking & Pruning

Understand how pruning eliminates impossible branches early and makes backtracking solutions more efficient.

Backtracking explores everything; pruning makes it explore only what CAN still work.

“Combination sum / subsets with constraints” → sort + cut branches early

Pattern 1: Combination Sum (candidates sorted, prune on remaining)

public List<List<Integer>> comboSum(int[] c, int target) {
    Arrays.sort(c);                 // enables the ✂ rule
    List<List<Integer>> res = new ArrayList<>();
    dfs(c, 0, target, new ArrayList<>(), res);
    return res;
}

void dfs(int[] c, int i, int rem,
         List<Integer> cur, List<List<Integer>> res) {
    if (rem == 0) { res.add(new ArrayList<>(cur)); return; }
    for (int j = i; j < c.length; j++) {
        if (c[j] > rem) break;      // ✂ PRUNE: rest are bigger
        cur.add(c[j]);
        dfs(c, j, rem - c[j], cur, res);
        cur.remove(cur.size() - 1);
    }
}
def combo_sum(candidates, target):
    candidates.sort()               # enables the ✂ rule
    res, cur = [], []

    def dfs(i, rem):
        if rem == 0:
            res.append(cur[:])
            return
        for j in range(i, len(candidates)):
            if candidates[j] > rem:
                break               # ✂ PRUNE: rest are bigger
            cur.append(candidates[j])
            dfs(j, rem - candidates[j])
            cur.pop()

    dfs(0, target)
    return res
vector<vector<int>> res;
vector<int> cur;

void dfs(vector<int>& c, int i, int rem) {
    if (rem == 0) { res.push_back(cur); return; }
    for (int j = i; j < (int)c.size(); j++) {
        if (c[j] > rem) break;      // ✂ PRUNE: rest are bigger
        cur.push_back(c[j]);
        dfs(c, j, rem - c[j]);
        cur.pop_back();
    }
}

vector<vector<int>> comboSum(vector<int> c, int target) {
    sort(c.begin(), c.end());
    dfs(c, 0, target);
    return res;
}
function comboSum(candidates, target) {
  candidates.sort((a, b) => a - b); // enables the ✂ rule
  const res = [],
    cur = [];

  const dfs = (i, rem) => {
    if (rem === 0) {
      res.push([...cur]);
      return;
    }
    for (let j = i; j < candidates.length; j++) {
      if (candidates[j] > rem) break; // ✂ PRUNE: rest are bigger
      cur.push(candidates[j]);
      dfs(j, rem - candidates[j]);
      cur.pop();
    }
  };

  dfs(0, target);
  return res;
}

Three classic prunes:

PruneWhere it firesWhy valid
c[j] > rem → breakloop startarray sorted ⇒ all later candidates also too big
i (not j+1) recursionrecursive callcombinations not permutations — kills duplicate orderings
skip duplicates if j > i && c[j]==c[j-1] continueloop startidentical values at same level produce identical subtrees

Pattern 2: Subsets with Sum Bound

Watch the +2 branch get fully explored while the pruner kills junk before it’s born. Press ▶.

Subset Sum with Pruning

Find subsets of [2,3,5] that sum to a target (8) using backtracking with pruning.

Each node is a take/skip decision on the next candidate. As soon as a partial sum exceeds the target (or, with sorted candidates, exceeds what's left), the whole branch is cut — sums only grow, so nothing later can rescue it. Sorting enables a total prune; the exponential tree collapses to almost nothing.

TREE VISUALIZER
Steps –
{}+2E2+2 +3+2 E3E2+3E2E3
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        dfs(i, remaining):
                      
                        2
                          if remaining == 0: record subset ✓
                      
                        3
                          if remaining < 0 or i == n: return   # PRUNE / leaf
                      
                        4
                          # only if candidates sorted can we prune harder:
                      
                        5
                          if candidates[i] > remaining: return # ✂ no future fits
                      
                        6
                          dfs(i+1, remaining - c[i])           # take
                      
                        7
                          dfs(i+1, remaining)                  # skip
                      
void subsets(int[] nums, int i, int sum, int limit,
             List<Integer> cur, List<List<Integer>> res) {
    if (sum > limit) return;        // ✂ whole branch is dead

    if (i == nums.length) { res.add(new ArrayList<>(cur)); return; }

    cur.add(nums[i]);                       // take
    subsets(nums, i+1, sum + nums[i], limit, cur, res);
    cur.remove(cur.size() - 1);             // BACKTRACK

    subsets(nums, i+1, sum, limit, cur, res); // skip
}
def bounded_subsets(nums, limit):
    res, cur = [], []

    def dfs(i, total):
        if total > limit:
            return              # ✂ whole branch is dead
        if i == len(nums):
            res.append(cur[:])
            return
        cur.append(nums[i])             # take
        dfs(i + 1, total + nums[i])
        cur.pop()                        # BACKTRACK
        dfs(i + 1, total)                # skip

    dfs(0, 0)
    return res
void subsets(vector<int>& nums, int i, int sum, int limit,
             vector<int>& cur, vector<vector<int>>& res) {
    if (sum > limit) return;     // ✂ whole branch is dead
    if (i == (int)nums.size()) { res.push_back(cur); return; }

    cur.push_back(nums[i]);                  // take
    subsets(nums, i+1, sum + nums[i], limit, cur, res);
    cur.pop_back();                           // BACKTRACK

    subsets(nums, i+1, sum, limit, cur, res); // skip
}
function boundedSubsets(nums, limit) {
  const res = [],
    cur = [];

  const dfs = (i, total) => {
    if (total > limit) return; // ✂ whole branch is dead
    if (i === nums.length) {
      res.push([...cur]);
      return;
    }
    cur.push(nums[i]); // take
    dfs(i + 1, total + nums[i]);
    cur.pop(); // BACKTRACK
    dfs(i + 1, total); // skip
  };

  dfs(0, 0);
  return res;
}

Even stronger: sort first, then prune when sum + suffixSum(i) can never reach a minimum bound — you can prove entire levels unreachable without visiting them.

Every prune must be provably safe: “nothing below this node can succeed.” Guessy cuts lose answers.

Common Mistakes

  • Pruning before sorting (the break trick silently skips valid answers).
  • Cutting branches that could still succeed (rem == 0 vs rem <= 0 confusion).
  • Duplicate results from reusing elements or unsorted candidate arrays.
  • Deep-copying into results incorrectly (res.add(cur) stores a reference!).

Complexity

MetricNo pruningWith pruning
TimeO(2^n) alwaysO(2^n) worst, typically far less
SpaceO(n) depthO(n)

My Private Notes

Notes are auto-saved locally to this device.