Combination Sum
Find every combination that sums to a target, reusing numbers freely, and prune with a sorted break.
Examples
2 + 2 + 3 = 7 uses 2 twice, which is allowed; 7 on its own is the other.
Three combinations; no order within or between them matters.
The only candidate is already bigger than the target.
Problem Understanding
Given an array of distinct integers candidates and a target, return a list of all unique combinations where the chosen numbers sum to target.
Key Rule: The same number may be chosen from candidates an unlimited number of times.
Algorithm Strategy
Sort the candidates first. Then backtrack(start, remaining) tries each candidate from start onwards:
- Too big? If
candidates[i] > remaining, break — the list is sorted, so every candidate after it is too big as well. - Choose it: append it and subtract it from
remaining. - Explore with
backtrack(i, …)— the samei, because a number may be used again. - Unchoose: pop it before trying the next candidate.
When remaining reaches 0 the path is a combination: record it and return.
Passing i rather than 0 is what keeps each combination unique: a call never goes back to a smaller candidate, so [2, 2, 3] is built once and [3, 2, 2] never is.
Interactive Visualization
Every node is one call to backtrack. Its label is the candidate that call added, and the number under it is what is still left to make — a node reading 0 is a combination.
A red node is the one candidate a call looked at and rejected with break: its number goes negative. The candidates after it are never looked at, so they are not drawn at all — that missing part of the tree is the saving. Try Unsorted to see why the sort has to come first.
Dry Run
Tracing candidates = [2, 3], target = 5.
| # | Call | Path | What happens |
|---|---|---|---|
| 1 | backtrack(0, 5) |
[] |
2 ≤ 5: choose 2 → backtrack(0, 3) |
| 2 | backtrack(0, 3) |
[2] |
2 ≤ 3: choose 2 → backtrack(0, 1) |
| 3 | backtrack(0, 1) |
[2, 2] |
2 > 1: break — 3 is never tried. Return |
| 4 | backtrack(0, 3) |
[2] |
Pop 2. 3 ≤ 3: choose 3 → backtrack(1, 0) |
| 5 | backtrack(1, 0) |
[2, 3] |
Nothing left: record [2, 3], return |
| 6 | backtrack(0, 3) |
[2] |
Pop 3. Loop done — return |
| 7 | backtrack(0, 5) |
[] |
Pop 2. 3 ≤ 5: choose 3 → backtrack(1, 2) |
| 8 | backtrack(1, 2) |
[3] |
3 > 2: break. Return |
| 9 | backtrack(0, 5) |
[] |
Pop 3. Loop done — return |
Result: [[2, 3]]. Row 8 starts at index 1, so it never goes back to 2 — which is why [3, 2] is not produced as well.
Edge Cases & Common Mistakes
Watch out for these pitfalls:
Reuse vs. move on: recurse with
ito allow the same number again. Passingi + 1silently solves a different problem (Combination Sum II, each number once).The break needs the sort:
breakis only safe because every later candidate is at least as big. On unsorted input it would skip combinations that exist — usecontinuethere, or sort first as this solution does.No combination at all:
[2]with target 1 returns[]— the root rejects its only candidate and records nothing. Return the empty list, not[[]].Zero and negatives: LeetCode guarantees candidates of at least 2. A 0 would let a path grow forever without changing
remaining, and a negative would break the pruning argument.
Solution
One algorithm in all six languages — the lines light up as the figure above steps.
Combination Sum Code
1var combinationSum = function(candidates, target) {2 candidates.sort((a, b) => a - b);3 const result = [];4 const path = [];56 const backtrack = (start, remaining) => {7 if (remaining === 0) {8 result.push([...path]);9 return;10 }11 for (let i = start; i < candidates.length; i++) {12 if (candidates[i] > remaining) {13 break;14 }15 path.push(candidates[i]);16 backtrack(i, remaining - candidates[i]);17 path.pop();18 }19 };2021 backtrack(0, target);22 return result;23};