LeetCode 39 · Medium · Backtracking

Combination Sum

Given distinct positive integers candidates and a target, return every combination of candidates that adds up to the target. A candidate may be used any number of times; combinations that differ only in order count once.

O(2ᵗ)time, t = target / min candidate
O(t)recursion depth
reuse or move ontwo branches per call

1–4 distinct integers from 2 to 20 · target 1–20 · capped at 120 tree nodes and 250 steps

totalvstarget

candidates i points at the candidate this call may reuse · ×n = copies in cur · faded = moved past

cur the combination on the current path

decision tree node = running total · left edge reuses candidates[i] · right edge moves past it · dashed = dead end

res 0 combinations

private List<List<Integer>> res;private int[] candidates;private int target;public List<List<Integer>> combinationSum(int[] candidates, int target) { this.res = new ArrayList<>(); this.candidates = candidates; this.target = target; dfs(0, new ArrayList<>(), 0); return res;}private void dfs(int i, List<Integer> cur, int total) { if (total == target) { res.add(new ArrayList<>(cur)); return; } if (i >= candidates.length || total > target) { return; } cur.add(candidates[i]); // reuse candidates[i] dfs(i, cur, total + candidates[i]); cur.remove(cur.size() - 1); dfs(i + 1, cur, total); // never use it again}
i
—
cur
[]
total
0
res.size()
0

Why it works

  1. Brute force tries every ordered sequence of candidates up to the target, then sorts each hit and dedupes. Orders explode factorially and most of the work rebuilds the same multiset.
  2. Decide candidates in index order. A call either reuses candidates[i] (stay at i) or gives it up for good (go to i + 1). Each combination therefore has exactly one path: all its 2s, then all its 3s, and so on. No duplicates, no dedupe.
  3. Depth is bounded by target / min. Each left edge adds at least the smallest candidate, so a path has at most t = target / min left edges, and the tree has O(2ᵗ) nodes. Stack depth is O(t) plus the number of candidates.
  4. Pitfall: recursing with i + 1 after taking. That turns it into Combination Sum II (each value once) and misses [2,2,3]. Taking must stay at i.
  5. Prune earlier: sort the candidates and return as soon as total + candidates[i] > target, since every later candidate is larger too. That removes every dead end with a > badge in the tree.