Combinations That Reach a Target

You get an array candidates of different positive integers and a positive integer target.

You can use each candidate as many times as you want. Return every combination of candidates whose sum is exactly target. Two combinations are different if some number is used a different number of times. Do not return the same combination twice.

Output order

• Write the numbers inside each combination in non-decreasing order. For example, write [2, 2, 5], not [5, 2, 2].
• Sort the list of combinations from smallest to largest. To compare two combinations, look at the first position where they differ; the one with the smaller number there comes first. So [2, 2, 5] comes before [2, 7], because 2 < 7 at the second position.

If no combination works, return an empty array []. The candidates array is not sorted.

Hint

Sort the candidates first. Build a combination one number at a time. After you add the candidate at index i, the next number may only come from index i or later. This stops [2, 3] and [3, 2] from both appearing, and it produces the combinations already in the required order. Stop early when a candidate is larger than what is left of the target.