Python 2.7 - find combinations of numbers in a list that add to another number

Question

What I'm looking to do is find a way that I can have my code return all the combinations of values from a list that add to a variable, returning each answer as a list. For instance,

    target_number = 8
    usingnumbers =  [1, 2, 4, 8]
    returns:
    [8]
    [4, 4]
    [4, 2, 2]
    [4, 2, 1, 1]
    [4, 1, 1, 1, 1]
    [2, 2, 1, 1, 1, 1]
    [2, 1, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 1, 1, 1, 1]

And so on. I'd like repeated values to be discarded, for instance [4, 2, 2], [2, 4, 2], [2, 2, 4] are all technically valid, but I'd like just one of these to be shown. Ideally, I'd want the code to also return the number of times each number appears in each list, but I'm sure I can do that for myself.

Answer 1

In psuedocode:

1. subract the largest number from you list from your composed number,keep track of the number you started with
2. loop that until you can't anymore
3. move on to second largest etc
4. start this cycle again, but start with the number smaller than the last loop you did.

Not that difficult.

Answer 2

Not going to write code for you, but there is main idea:

Function F(n, (k1, k2, .. km)) - returns set of lists of numbers:

{(a11, ... a1i), (a21, ... a2i), ... (aj1, ... aji )}

There is recurrent relationship:

F(n, (k1, k2, .., km)) = union(
  (k1) (+) F(n - k1, (k1, k2, ... km)),
  (k2) (+) F(n - k2, (k2, k3, ... km)),
  ...
  (km) (+) F(n - km, (km))
)

Operation a (+) b is 'append a to each item of b'.

There is a few of many corner cases, but it's up to you.

Answer 3

This is a complete solution to the problem, the whole function is a big generator in disguise, the first for loop uses the smallest coin and in the second one, the smallest coin is discarded and the next big one is going to be the basis of our recursive function. If sum of current coins is equal to given number the list containing the coins is returned, if the sum is bigger then the number that list is discarded.

def changes(number, coins_available, coins_current):
    if sum(coins_current) == number:
        yield coins_current
    elif sum(coins_current) > number:
        pass
    elif coins_available == []:
        pass
    else:
        for c in changes(number, coins_available[:], coins_current + [coins_available[0]]):
            yield c
        for c in changes(number, coins_available[1:], coins_current):
            yield c

n = 40
coins = [1,2,5,10,20,50,100]

solutions = [sol for sol in changes(n, coins, [])]

for sol in solutions:
    print sol

print 'least coins used solution:', min(solutions, key=len)
print 'number of solutions', len(solutions)