Invoice Combination Sum
An invoice must be settled exactly using a fixed catalogue of line-item amounts, and each amount can be billed any number of times. Enumerate every distinct combination of line items that sums to the invoice total.
Problem
Given an array of distinct positive integers candidates and a target integer, return all unique combinations of candidates whose elements sum to target. The same candidate may be chosen an unlimited number of times. Two combinations are unique if their multiset of chosen numbers differs.
Input
An array candidates of distinct positive integers (1 ≤ candidates.length ≤ 30, 1 ≤ value ≤ 200) and a positive integer target (1 ≤ target ≤ 500).
Output
A list of combinations; each combination is a list of integers summing to target.
Constraints
- Candidates are distinct positive integers
- Each candidate may be reused unlimited times
- No duplicate combinations in the output
Examples
Example 1
Input
candidates = [2, 3, 6, 7], target = 7
Output
[[2, 2, 3], [7]]
2+2+3 = 7 and 7 = 7 are the only combinations.
Example 2
Input
candidates = [2, 4], target = 5
Output
[]
No multiple of 2 and 4 sums to the odd total 5.