Combination Sum
Last Updated: March 29, 2026
Understanding the Problem
We're given an array of distinct positive integers and a target sum. We need to find every way to pick numbers from the array (with unlimited reuse) that add up exactly to the target. The order of numbers in a combination doesn't matter, so [2, 2, 3] and [2, 3, 2] are the same combination and should only appear once.
What makes this problem interesting is the "unlimited reuse" aspect. Unlike problems where each element can only be used once, here we can pick the same candidate as many times as we want. This means the search space is potentially large, but the constraints (target up to 40, candidates at least 2) keep things manageable.
The key observation is that this is a classic backtracking problem. We systematically explore all ways to build up to the target by trying each candidate and recursing with the remaining sum. To avoid duplicate combinations, we enforce an ordering: once we move past a candidate, we never go back to it.
Key Constraints:
1 <= candidates.length <= 30→ Up to 30 candidates, which is small enough for backtracking. With good pruning, we won't hit time limits.2 <= candidates[i] <= 40→ Every candidate is at least 2. This means the maximum depth of recursion is target / min(candidates) = 40 / 2 = 20. That's shallow.1 <= target <= 40→ A small target keeps the total number of valid combinations manageable (the problem guarantees fewer than 150 combinations).- All elements are distinct → No need to worry about duplicate candidates producing duplicate combinations.
Approach 1: Brute Force (Generate All Combinations)
Intuition
The most direct way to think about this: for each candidate, decide how many times to include it (0, 1, 2, ... up to target / candidate), then move on to the next candidate. After we've made a decision for every candidate, check if the total sum equals the target.
This is essentially enumerating every possible "frequency vector." If we have candidates [2, 3, 7] and target 7, we're trying all combinations like (0 twos, 0 threes, 0 sevens), (1 two, 0 threes, 0 sevens), ..., (3 twos, 0 threes, 0 sevens), (0 twos, 1 three, 0 sevens), and so on. Most of these will overshoot the target or fall short, but we check every possibility.
This approach does no pruning at all. It generates all possible frequency assignments and only filters valid ones at the end.
Algorithm
- Start with the first candidate and an empty combination.
- For the current candidate, try using it 0 times, 1 time, 2 times, etc., up to the point where the sum would exceed the target.
- For each choice, move on to the next candidate and repeat.
- After processing all candidates, if the running sum equals the target, record the combination.
- Collect all valid combinations and return them.
Example Walkthrough
Code
- Time Complexity: O(N^(T/M)). Where N is the number of candidates, T is the target value, and M is the minimum candidate value. The recursion tree has a branching factor of N and depth T/M. Each valid combination takes O(T/M) to copy.
- Space Complexity: O(T/M). The recursion stack depth is bounded by the number of candidates, and the current list holds at most T/M elements. Output space is not counted.
This approach works correctly but doesn't abandon hopeless branches early. What if instead of deciding the full count upfront, we added one candidate at a time and checked the remaining target after each addition?
Approach 2: Backtracking with Pruning (Optimal)
Intuition
Instead of deciding how many times to use each candidate upfront, backtracking takes a more incremental approach: pick one candidate, subtract it from the target, and recurse with the reduced target. If the remaining target hits zero, we've found a valid combination. If it goes negative, we went too far and backtrack.
The critical insight for avoiding duplicates is this: we maintain a "start index." When we pick a candidate at index i, the next recursive call can only consider candidates at index i or later. This means we never pick candidate[2] after candidate[3], which prevents generating [3, 2] as a separate combination from [2, 3].
Sorting the candidates first gives us an extra pruning advantage. If we're iterating through candidates and the current one exceeds the remaining target, every subsequent candidate will too (since they're sorted in ascending order). So we can break out of the loop immediately instead of checking each one.
The backtracking approach works because it systematically explores the decision tree while maintaining two invariants. First, by always iterating from start to the end, we never revisit earlier candidates, which guarantees each combination appears exactly once. Second, by sorting and breaking when a candidate exceeds the remaining target, we prune entire subtrees that can't possibly lead to valid combinations.
The "pass i instead of i + 1" detail is what allows unlimited reuse. When we pick candidate[i], the next call starts from i again, so we can pick the same candidate repeatedly. But we never go back to candidate[i-1], preventing duplicates like [3, 2] when we already found [2, 3].
Algorithm
- Sort the candidates array in ascending order.
- Start a recursive backtracking function with the full target and start index 0.
- If the remaining target is 0, we found a valid combination. Add it to the result.
- Iterate through candidates starting from the current start index.
- If the current candidate exceeds the remaining target, break (all further candidates are larger).
- Add the candidate to the current combination.
- Recurse with the reduced target and the same start index (since we can reuse the candidate).
- Remove the last candidate (backtrack) and try the next one.
Example Walkthrough
Code
- Time Complexity: O(N^(T/M)). Where N is the number of candidates, T is the target, and M is the minimum candidate value. The recursion tree has branching factor up to N and depth up to T/M. In practice, sorting and pruning cut this down significantly.
- Space Complexity: O(T/M). The recursion depth is at most T/M, and the current list holds at most T/M elements. Output space is not counted.