All Sum Combinations

Given an array values of distinct positive integers and a positive integer target, return every combination of values whose sum is exactly target. Each value may be used any number of times in a combination; two combinations are different when they use at least one value a different number of times.

To make the answer unique, return the combinations in the following canonical order:

• Within each combination, list the chosen values in non-decreasing order.
• List the combinations in lexicographic order: compare two combinations element by element and put the one with the smaller value at the first difference first; if one is a prefix of the other, the shorter one comes first.

If no combination sums to target, return an empty array.

Examples

Example 1

Input: values = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 + 2 + 3 = 7 (the value 2 is used twice) and 7 = 7. No other combination reaches 7.

Example 2

Input: values = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: Three combinations sum to 8, listed in lexicographic order.

Example 3

Input: values = [2], target = 1
Output: []
Explanation: No multiple of 2 equals 1.