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).

Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
 
Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Solution

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 2 can be appended repeatedly. Keeping start non-decreasing across levels is also what dedupes - [2, 2, 3] and [3, 2, 2] 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 [2, 3, 6, 7], target 7: from 2 we reach [2, 2, 3] (remaining hits 0); 6 and 7 from the top give [7]; 6 alone leaves remaining 1 and breaks. Two combinations.

Edge cases: A candidate larger than the target breaks immediately and contributes nothing ([2], target 1 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.