Combination Sum

def combination_sum(nums, target):
    nums.sort()
    out = []
    def go(start, remain, picks):
        if remain == 0:
            out.append(picks[:])     # save a copy
            return
        for i in range(start, len(nums)):
            if nums[i] > remain:
                break                # too big: stop
            picks.append(nums[i])
            go(i, remain - nums[i], picks)   # same i
            picks.pop()              # backtrack
    go(0, target, [])
    return out

Combination Sum. Given distinct positive numbers and a target, return every combination that adds up to the target. Each number can be used again and again.

Take two, three, six and seven, with a target of seven. Picture a cauldron that must fill to exactly seven. Two, two and three works, and so does seven alone.

The naive way tries pours in every order. But two, two, three; two, three, two; and three, two, two are the same recipe, so the answers repeat.

The fix is backtracking with a start index. After pouring a number, you may pour it again or any number to its right, never one to its left. So each recipe is built in only one order. And sort the numbers: once one overflows, every bigger one would too, so stop.

In code, a helper takes a start index, the amount remaining, and the picks. When nothing remains, save a copy. Otherwise, loop from the start, break if the number is too big, add it, recurse with the same index, and pop it back off.

Let's brew. Two, two, two leaves one, and nothing fits, so back up. Two, two, three hits seven exactly: save it. Two, three leaves two, but we can't go back to two. Three, three leaves one. Six leaves one. Dead ends. Last, seven alone: save it.

The time is exponential, bounded by the partial recipes explored: roughly n to the power of target over the smallest number. The space is the recursion depth, at most target over the smallest number.

Pour in order, reuse freely, stop at the brim. That's Combination Sum.