Combination Sum
Problem Statement
Given an array of distinct positive integers candidates and a positive integer target, return all unique combinations of candidates whose selected numbers sum to target. You may choose the same candidate an unlimited number of times. The answer may be returned in any order.
Input
An integer array candidates containing distinct positive values, and an integer target.
Output
A list of combinations where each combination sums to target and may reuse a candidate multiple times.
Constraints
- •
1 <= candidates.length <= 30 - •
2 <= candidates[i] <= 40 - •
All elements of candidates are distinct - •
1 <= target <= 40
Examples
Example 1
candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]Example 2
candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]Example 3
candidates = [2], target = 1
[]Learning Objectives
- Distinguish unlimited reuse from the no-reuse combination template.
- Use the same **start** index after choosing a candidate that may be reused.
- Sort candidates so **candidate > remaining** can end the loop early.
- Track remaining target instead of recomputing the path sum from scratch.
Intuition
Pattern Recognition
This is still a choose-without-order problem: [2,2,3] and [3,2,2] represent the same combination. The start-index technique is still the right duplicate-prevention tool. The twist is reuse: after choosing candidate at index i, the next recursive call starts at i again, not i + 1.
Because every number is positive, the running sum only increases as the path grows. That gives a clean pruning rule: once the remaining target becomes negative, the branch cannot recover. Sorting improves the rule further: when the current candidate is larger than the remaining target, all later candidates are also too large, so the loop can break.
Common mistakes
- ×Recursing with **i + 1** after every choice, which incorrectly forbids using a candidate more than once.
- ×Recursing from **0** after every choice, which creates duplicate orderings of the same combination.
- ×Continuing the loop after a sorted candidate exceeds the remaining target.
- ×Adding a path when the sum is below target just because no more candidates were tried.
Algorithm Explanation
State
Each frame carries start, the first candidate index allowed in this combination suffix, remaining, the amount still needed to reach target, and path, the chosen values.
Recursion tree
For sorted [2,3,6,7] and target 7, the root first chooses 2 and stays at index 0, allowing another 2. That path reaches [2,2] with remaining 3, then chooses 3 and adds [2,2,3]. The branch [2,2,2] has remaining 1, so candidates 2, 3, 6, and 7 are too large and the branch stops. Back at the root, choosing 3 cannot later choose 2, so order duplicates are avoided. Choosing 7 reaches remaining 0 and adds [7].
Pruning
All values are positive. If remaining == 0, the path is complete. If a sorted candidate is greater than remaining, break the loop because all later candidates are greater too. Reusing is controlled deliberately by calling the helper with the same index i.
Algorithm
- Sort candidates.
- Start DFS with start = 0, remaining = target, and an empty path.
- If remaining == 0, copy path into the answer.
- Loop i from start to the end of the array.
- Break when candidates[i] > remaining.
- Choose candidates[i], recurse with start = i and the reduced remaining target, then unchoose it.
Solutions
Solution: Sorted start-index DFS with reusable candidates
Sorting lets the DFS stop a branch as soon as a candidate is too large for the remaining target. Passing i back into the recursive call is the key reuse rule; passing i + 1 would solve a different problem.
Step-by-step
- Sort the candidates in ascending order.
- Call the helper with start index 0 and the full target as the remaining sum.
- When remaining becomes 0, copy the current path into the result.
- For each candidate from start onward, stop if it exceeds the remaining sum.
- Add the candidate, recurse from the same index to allow reuse, then remove it before trying the next candidate.
O(n^(target / minCandidate) * target / minCandidate)
O(target / minCandidate)
The maximum depth is bounded by repeatedly choosing the smallest candidate. The output size dominates for many inputs.
Java implementation
Dry Run
Sample input
candidates = [2,3,6,7], target = 7. The array is already sorted. Track remaining as part of the path summary.
| depth | start | choice | path and sum | action |
|---|---|---|---|---|
| 0 | 0 | 2 | [2], remaining 5 | choose 2 and recurse from same index 0 |
| 1 | 0 | 2 | [2,2], remaining 3 | reuse 2 because start stayed at 0 |
| 2 | 0 | 2 | [2,2,2], remaining 1 | next candidate 2 is too large, prune |
| 2 | 0 | 3 | [2,2,3], remaining 0 | add combination |
| 1 | 0 | 3 | [2,3], remaining 2 | candidate 3 is now too large at next depth, prune |
| 0 | 0 | 3 | [3], remaining 4 | choose 3, recurse from index 1 |
| 1 | 1 | 3 | [3,3], remaining 1 | candidate 3 is too large, prune |
| 0 | 0 | 6 | [6], remaining 1 | next candidate 6 is too large, prune |
| 0 | 0 | 7 | [7], remaining 0 | add combination |
The same-index recursive call is why 2 can repeat, while the start index still prevents order duplicates like [3,2,2].
Interview Tips
Frame the problem as combinations over a sorted candidate list, not permutations. Then explicitly say the recursive start rule: reuse means call with i; no reuse means call with i + 1. That single sentence often separates correct solutions from near misses.
Likely follow-ups
- What changes if each candidate may be used at most once?
- How would you handle duplicate values in **candidates**?
- How would you return only the number of combinations instead of listing them?
- How would the solution change if negative numbers were allowed?
Similar Problems
Key Takeaways
- Unlimited reuse means recurse from the same candidate index.
- The start index still prevents permuted duplicates.
- Sorting enables an early break when a candidate exceeds the remaining target.
- Track **remaining** directly so the base case is **remaining == 0**.