LeetCode 40 · Medium · Backtracking

Combination Sum II

Given candidates that may repeat values and a target, return every distinct combination that adds up to the target. Each array position can be used at most once, and the answer must not list the same combination twice.

O(n · 2ⁿ)time
O(n)recursion depth
sort, skip equal siblingsno duplicate branches

1–10 integers from 1 to 20, repeats welcome · target 1–20 · capped at 120 tree nodes and 250 steps

targetprev

candidates, sorted blue = used on this path · i points at the loop index

cur the combination on the current path

decision tree node = target still to reach · one child per loop value · dashed “dup” = same value as the previous sibling, pruned

res 0 combinations

private List<List<Integer>> res;private int[] candidates;public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); this.candidates = candidates; res = new ArrayList<>(); backtrack(new ArrayList<>(), 0, target); return res;}private void backtrack(List<Integer> cur, int pos, int target) { if (target == 0) { res.add(new ArrayList<>(cur)); } if (target <= 0) { return; } int prev = -1; for (int i = pos; i < candidates.length; i++) { if (candidates[i] == prev) { continue; // same value as the last branch } cur.add(candidates[i]); backtrack(cur, i + 1, target - candidates[i]); cur.remove(cur.size() - 1); prev = candidates[i]; }}
pos, i
—
cur
[]
target left
—
pruned
0
res.size()
0

Why it works

  1. Brute force tries all 2ⁿ position subsets, keeps those that hit the target, then sorts each and dedupes with a set. Every combination built from different copies of a value is built again and thrown away.
  2. Equal siblings build equal subtrees. After sorting, two children of the same node that start with the same value lead to exactly the same combinations. The first one already covers every combination that uses that value here, including ones that take its later copies deeper down, so the second is pruned on sight.
  3. O(n · 2ⁿ) worst case. Without repeats the tree is the subset tree of n positions, and each answer is copied in O(n). Sorting the candidates means the target only falls along a path, and the stack is at most n deep.
  4. Pitfall: pruning equal values across levels. prev is local to one call. Skipping a value just because the parent used it would lose [1,1,6]. Only siblings are compared.
  5. Prune more: because the list is sorted, break as soon as candidates[i] > target; every later sibling overshoots too. The dashed “< 0” nodes are what that saves.