Combination Sum

Problem

Build systems track which package versions can satisfy a dependency: given a list of available version integers and a required total, find every multiset of versions that sums exactly to the target. Candidates may be reused unlimited times. Given distinct positive integers and a target, return all unique combinations that sum to target (each number may be used multiple times).

Example 1:

Input: candidates = [4, 5, 8], target = 13
Output: [[4, 4, 5], [5, 8]]

Example 2:

Input: candidates = [2, 5, 6], target = 12
Output: [[2, 2, 2, 2, 2, 2], [2, 2, 2, 6], [2, 5, 5], [6, 6]]

Constraints:

• 1 <= candidates.length <= 20
• 2 <= candidates[i] <= 20
• All candidates are distinct.
• 1 <= target <= 40

Solution Breakdown

Approach: Backtracking with a start index, reuse via index (not index + 1), and sort-enabled break pruning.

The recursion carries two pieces of state: start, the lowest candidate index still allowed, and remaining, how much of the target is left. The base case records path[:] exactly when remaining == 0 - unlike subsets, only complete sums are answers, not every node. Inside the loop the one change that enables reuse is the recursive call backtrack(index, remaining - candidates[index]): passing index instead of index + 1 keeps the same candidate available on the next level, so a value like 4 can be appended repeatedly. Keeping start non-decreasing across levels is also what dedupes - [4, 4, 5] and [5, 4, 4] would be the same multiset, and only the non-decreasing one is ever built. The candidates.sort() enables the break: once candidates[index] > remaining, every later candidate is at least as large, so the whole rest of the loop is hopeless and we exit it entirely rather than continue-ing past each. Trace [4, 5, 8], target 13: from 4 we reach [4, 4, 5] (remaining hits 0); 5 then 8 from the top give [5, 8]; 8 alone leaves remaining 5 and breaks. Two combinations.

Edge cases: A candidate larger than the target breaks immediately and contributes nothing ([3], target 2 returns []). A candidate exactly equal to the target forms a single-element combination.

Complexity: O(n^(target/min)) time, O(target/min) space - branching is bounded by how many times the smallest candidate fits into target; recursion depth is the path length.