Combination Sum

Given distinct candidate numbers and a target, return the count of unique combinations where the chosen numbers sum to the target. The same number may be reused unlimited times.

Example

Input: candidates 2 3 6 7, target 7 Output: 2 ([7] and [2, 2, 3])

Approach

Backtrack with a running remaining-target, but — since numbers can repeat — the recursive call for "use this candidate again" starts from the same index, not the next one. Only advance the index when moving on to a candidate you haven't tried at this position yet, which is what prevents duplicate combinations like [2,3,2] and [2,2,3] both being counted.

Input format

Line 1: candidates, space-separated Line 2: target

Print the number of unique combinations.