Every way to make the target

Given a list of distinct positive numbers and a target, list every combination that adds up to the target. A number may be used as many times as you like.

Two combinations are the same if they use the same numbers the same number of times, so 2 2 3 and 2 3 2 are one answer, not two. Print each combination's numbers in increasing order, one combination per line.

Sort the numbers first and print the combinations in the order the walk produces.

Worked example#

For [2, 3, 6, 7] with target 7:

2 2 3
7

2 + 2 + 3 is 7, and 7 on its own is 7. Nothing else works: 2 + 2 + 2 is 6 and adding anything overshoots.

The idea#

At each step, choose a number and subtract it from what is left. When what is left reaches zero you have an answer. If it goes below zero you have gone too far.

Two decisions make this correct rather than merely working.

Recurse on i, not i + 1. Staying at the same index is what allows a number to be used again. This is the one line that differs from every subset, and it is worth comparing them side by side.

Never go back to an earlier index. That is what stops 2 3 2 appearing after 2 2 3. By only ever moving forward, every combination is generated once, already in increasing order, and no separate de-duplication is needed.

walk(start, left):
    if left == 0: record, return
    for i from start to the end:
        if nums[i] > left: break
        choose nums[i]
        walk(i, left - nums[i])     # i, so it can be reused
        un-choose

The pruning#

Sort the numbers first. Then once nums[i] is bigger than what is left, everything after it is bigger too, so you can break out of the loop instead of continue.

On a list of twenty numbers with a target of forty, that turns a walk that explores hopeless branches into one that stops at the first number too large. The sort costs nothing next to the saving.

Constraints#

• 1 <= n <= 20, values distinct and between 2 and 40
• 1 <= target <= 40