Combination Sum

Problem

You are given an array of distinct positive integers candidates and a target integer target. Return every distinct combination of candidates whose values add up to target. Any candidate may be used any number of times. Two combinations are the same if they use the same values with the same multiplicities, regardless of order. The output may be in any order.

• Up to 25 candidate numbers, all distinct.
• Target is a positive integer up to 60.

Examples

• candidates = [3, 4, 8, 9], target = 9 → [[3,3,3], [9]]. 3+3+3 = 9 and 9 alone; [3,3,3] in any order is the same combination.
• candidates = [3, 4, 6], target = 10 → [[3,3,4], [4,6]].
• candidates = [3], target = 2 → []. No way to reach a smaller target than the only candidate.

Hints

1. Build the combination one candidate at a time and keep track of how much of the target is still unpaid.
2. To avoid generating [2,3] and [3,2] as separate answers, decide that candidates are added in non-decreasing index order.
3. Backtracking with a start index that does not advance when you reuse a candidate; sort the candidates so you can stop the loop as soon as one is too large.