You're given an array of distinct positive integers candidates and a target integer target. Return every unique combination of numbers from candidates that adds up to exactly target.
You may reuse the same number as many times as you like. A combination is defined by how many of each number it contains — so [2,2,3] and [2,3] are different answers, while [2,2,3] and [3,2,2] count as the same combination. You may return the combinations and the numbers within them in any order.
Every test is chosen so that fewer than 150 distinct combinations exist for the given input.
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] 2 + 2 + 3 = 7 (2 is reused), and 7 = 7. Those are the only two ways.
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Input: candidates = [2], target = 1 Output: [] The only number is 2, which already overshoots 1, so nothing sums to the target.
- 1 <= candidates.length <= 30 - 2 <= candidates[i] <= 40 - All elements of candidates are distinct. - 1 <= target <= 40 - Fewer than 150 unique combinations exist for any input.
Combination Sum is the gateway to backtracking with reuse — the same recursion that powers coin problems. We'll go from a clumsy "try everything" search to a lean, pruned walk that only ever moves forward.
In plain words: pick numbers (repeats allowed) so they add up to target, and collect each distinct group exactly once. Formally, find all multisets drawn from candidates whose elements sum to target.
Worked example — candidates = [2,3,6,7], target = 7
start empty, remaining = 7 take 2 -> rem 5 -> take 2 -> rem 3 -> take 3 -> rem 0 [2,2,3] take 7 -> rem 0 [7] answer: [[2,2,3],[7]]
Asking these before writing code shows you're mapping the input's guarantees onto your algorithm - exactly what an interviewer wants to see.
“Are the candidates guaranteed distinct and positive?”
Distinct means I never worry about duplicate denominations; all-positive means the running remainder only ever shrinks, so recursion is guaranteed to terminate.
“What do I return if nothing sums to the target?”
An empty list - for example target smaller than every candidate. I must not return a list containing an empty combination.
“How many combinations can there be, and how large is the target?”
The problem promises fewer than 150 combinations and a target up to 40, so an exponential search with good pruning comfortably fits the time limit.
Before I code, a few clarifying questions.
Can I assume the candidates are distinct and strictly positive, so the remaining target always decreases?
And if no combination reaches the target, I return an empty list rather than a list with an empty group - correct?
Because a number can be used again and again, after we pick candidates[i] we should recurse still allowing index i - not move past it. This one detail is the entire difference from a plain subset search.
pick candidates[i] -> recurse from i (can pick it again) skip candidates[i] -> recurse from i + 1 (never again)
[2,3] and [3,2] are the same combination. If we always extend using candidates at index >= start (a non-decreasing choice), each multiset is built in exactly one canonical order - duplicates can never appear.
Sort candidates ascending. Inside the loop, the first time candidates[i] > remaining, every later candidate is also too big - so we break instead of wasting time on dead branches.
sorted [2,3,6,7], remaining = 1 2 > 1 -> break immediately, no branch explored
| Brute force | Optimal (pruned) | |
|---|---|---|
| Sorting | none | O(N log N) |
| Dead branches | explored to the end | cut early by break |
| Extra space | O(target / min) | O(target / min) |
Both approaches live in the same exponential family, but sorting plus the early break lets the optimal version abandon hopeless branches instantly. The full code for each is in the Approaches selector below.
Key takeaway
Combination Sum is backtracking with a twist: recurse on the same index to allow reuse, carry a start index to forbid going backwards (no duplicates), and sort so you can break early. Change that one recursion from i to i + 1 and you get "use each number at most once" instead.
sort(candidates)
dfs(start, remaining):
if remaining == 0: record a copy of the current combo; return
for i from start to end:
if candidates[i] > remaining: break # sorted -> rest too big
choose candidates[i]
dfs(i, remaining - candidates[i]) # i, not i+1 -> reuse
un-choose candidates[i]