Combination Sum
Problem statement
You're given a list of distinct positive integers, candidates, and a target value. Find every unique combination of numbers from candidates that adds up exactly to target. Any number can be reused as many times as you like within a single combination, and two combinations only count as different if they use a different number of copies of at least one value — order doesn't matter.
Examples
Example 1
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Explanation: 2 + 2 + 3 = 7, reusing 2 twice. 7 on its own also equals 7. No other combination of these numbers adds up to 7.
Example 2
Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Explanation: three different ways to reach 8: four 2s, one 2 and two 3s, or one 3 and one 5.
Example 3
Input: candidates = [2], target = 1
Output: []
Explanation: the only number available is bigger than the target, so no combination — not even using it zero times, since an empty combination doesn't count — can reach 1.
Hints
Approach
Optimal: Sort first, then prune early
Intuition
The brute-force version can waste time exploring paths that are obviously doomed — for instance, once the running total plus the smallest remaining candidate already exceeds the target, nothing smaller is coming to save it. Sorting the candidates first makes this easy to detect: walk through them in increasing order, and the moment adding the current one would overshoot, every candidate after it (being equal or bigger) would overshoot too — so the whole rest of that loop can be skipped in one step, not one candidate at a time.
Steps
- Sort the candidates in increasing order.
- Define a recursive step that tracks the current combination, its running total, and the earliest index it's still allowed to use.
- If the running total equals
target, save a copy of the combination and return. - Otherwise, loop through the candidates starting at the allowed index. For each one: if adding it would push the total past
target, stop the loop immediately — every later candidate is at least as big, so none of them can work either. - Otherwise, include this candidate, recurse (staying at this same index, since repeats are allowed), then remove it again to backtrack and try the next candidate in the loop.
Dry run
candidates = [2, 3, 6, 7] sorted stays [2, 3, 6, 7], target = 7.
| combination so far | total | next candidate tried | what happens |
|---|---|---|---|
| [2, 2, 2] | 6 | 2 (6 + 2 = 8) | over target — stop the whole loop here, never even look at 3, 6, or 7 |
| [2, 2] | 4 | 3 (4 + 3 = 7) | exact match → [2, 2, 3] found |
| [2, 2] | 4 | 6 (4 + 6 = 10) | over target — stop the loop |
| [2] | 2 | 3 (2 + 3 = 5), then 3 again (5 + 3 = 8) | 8 is over — stop that inner loop |
| [] | 0 | 7 (0 + 7 = 7) | exact match → [7] found |
The brute-force walkthrough had to try 3, 6, and 7 one at a time after [2, 2, 2] overshot; here, sorting means the very first failed check (6 + 2 = 8) is enough to rule out the rest of that entire loop in one step. The final result is the same: [[2, 2, 3], [7]].
Edge cases: if the smallest candidate is already bigger than the target (as in Example 3), the very first loop check fails immediately and the recursion returns with nothing — no wasted exploration at all.
Complexity
Time O(2^(t/m)) - the same worst-case shape as the brute-force approach, since the number of valid combinations doesn't change. What improves is how much wasted work happens on the way: many dead-end paths are cut off before they're ever explored.
Space O(t/m) - the same recursion depth as before.
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
res = []
nums = sorted(candidates)
def dfs(start: int, cur: list[int], total: int) -> None:
if total == target:
res.append(cur.copy())
return
for j in range(start, len(nums)):
if total + nums[j] > target:
return
cur.append(nums[j])
dfs(j, cur, total + nums[j])
cur.pop()
dfs(0, [], 0)
return res
if __name__ == "__main__":
print(Solution().combinationSum([2, 3, 6, 7], 7)) # [[2,2,3],[7]]
print(Solution().combinationSum([2, 3, 5], 8)) # [[2,2,2,2],[2,3,3],[3,5]]
print(Solution().combinationSum([2], 1)) # []RecapThe whole problem in a few lines, for the night before
- Spot it: "find combinations from a set of numbers that reach a target, numbers reusable" — backtracking with a repeat-allowed choice at each step
- Idea: recurse with (index, current combination, running total); include a candidate and stay at its index (allows reuse), or move to the next index and skip it
- Cost: O(2^(t/m)) time, O(t/m) space, where t is the target and m is the smallest candidate
- Trap: advancing the index after including a candidate — that silently turns "unlimited reuse" into "use each number once"
Interview follow-ups
What if each candidate can only be used once instead of unlimited times?
Move to the next index after including a candidate, instead of staying on the same one — that's the only change needed to stop reuse. This is the shape of the related problem "Combination Sum II," which also has to handle duplicate values in the input to avoid producing the same combination twice.
The candidates list could have thousands of entries, and the target could be large. How would you keep this from blowing up?
The exponential cost comes from the number of valid combinations themselves, not from inefficiency in the search, so there's no way to avoid enumerating all of them if the caller truly wants every combination listed. If only a count of combinations is needed rather than the combinations themselves, switch to a dynamic programming approach that counts ways to build each total from 0 up to the target — that stays polynomial in the target and the number of candidates, since it never has to materialize each combination.
Frequently asked questions
Because numbers can be reused, "using candidate i" doesn't use it up — it should still be available on the very next step. Moving to i + 1 after using it would make each number usable only once, turning this into a different problem (no repeats allowed).
Because the problem only cares about how many of each number are used, not the order they appear in — [2, 2, 3] and [2, 3, 2] are the same combination. Always choosing candidates in non-decreasing index order guarantees each valid multiset of numbers is only ever built once, instead of once per ordering.
There's a DP formulation (building up, for every value from 0 to target, the combinations that reach it), but it doesn't change the fundamental cost — the number of valid combinations can still be exponential in the worst case, and DP mainly helps when you want a count rather than the actual list of combinations. Since this problem asks for every combination explicitly, backtracking with pruning is the more natural fit, and it's what interviewers expect here.
Picking a set of fixed-size building blocks (VM sizes, batch chunk sizes, buffer allocations) that add up exactly to a target capacity or budget, where the same size can be used more than once, is the same shape — enumerate every way to hit an exact total using a small set of reusable, distinct sizes.