List of all possible monetary totals from a set of cash

This code prints out a list of all the possible sums that can be made from a set of cash.

For example, say you have 2 fives and 2 tens in your wallet. With these, you can make exact change for $0, $5, $10, $15, $20, $25, and $30.

import itertools
cash = {1: 1, 5: 3, 10: 2} # Keys are denominations (e.g. $1 bill)
                        # Values are the numbers of bills (e.g. three $1 bills)
totals = set() # Set of possible totals 
cash_list = [i for i in sorted(cash) for j in range(cash[i])] # List of all bills
for r in range(len(cash_list)+1):
    for subset in itertools.combinations(cash_list, r): # All the bill combinations
        totals.add(sum(subset)) # Record the total of the bills
print(sorted(list(totals))) # Print all possible totals

Output:

[0, 1, 5, 6, 10, 11, 15, 16, 20, 21, 25, 26, 30, 31, 35, 36]

1. Review

-
The data structure cash is a map from denomination to the count of the bills in that denomination. This is a representation of a multiset, and it's a good idea here to use the built-in collections.Counter:

from collections import Counter
cash = Counter({1: 1, 5: 3, 10: 2})

Now you can replace this line:

cash_list = [i for i in sorted(cash) for j in range(cash[i])]

with a call to the Counter.elements method:

cash_list = list(cash.elements())

-
The code is not organized into functions. This makes it hard to test and hard to measure the performance. It would be better to write something like this:

from collections import Counter
from itertools import combinations

def change(cash):
    """Given a map from denomination to the count of bills in that
    denomination, return the set of values that can be made using a
    subset of the bills.

    """
    totals = set() # Set of possible totals 
    cash_list = list(Counter(cash).elements()) # List of all bills
    for r in range(len(cash_list)+1):
        for subset in combinations(cash_list, r):
            totals.add(sum(subset))
    return totals

Now we can easily test it:

>>> change({1:1, 2:1, 4:1, 8:1}) == set(range(16))
True

and measure its performance:

>>> from timeit import timeit
>>> timeit(lambda:change({1:20}), number=1)
0.6443959611933678

1. Performance

The algorithm loops over all subsets of bills. But this doesn't take advantage of the fact that bills of the same denomination are indistinguishable. For example, we know that

change({1:25}) == set(range(26))

since if you have twenty-five $1 bills, you can make change for all dollar amounts from $0 to $25. But this calculation, that should be trivial, takes a very long time:

>>> timeit(lambda:change({1:25}), number=1)
22.855976961087435

And good luck waiting for, say, change({1:100}) to finish running. So we can improve the performance in these cases by taking advantage of the fact that if have \$n\$ bills of denomination \$d\$, the possible values are \$0, d, 2d, \ldots, nd\$, that is, range(0, (n + 1) * d, d). Using itertools.product we can write it like this:

from collections import Counter
from itertools import product

def change2(cash):
    """Given a map from denomination to the count of bills in that
    denomination, return the set of values that can be made using a
    subset of the bills.

    """
    ranges = [range(0, (n + 1) * d, d) for d, n in Counter(cash).items()]
    return set(map(sum, product(*ranges)))

This is slightly slower than the original code in cases where all the denominations are different:

>>> timeit(lambda:change({2**i:1 for i in range(20)}), number=1)
0.9978475249372423
>>> timeit(lambda:change2({2**i:1 for i in range(20)}), number=1)
1.0107885741163045

but it is massively faster in cases where there are many bills of a denomination:

>>> timeit(lambda:change2({1:25}), number=1)
0.000085500068962574

StackExchange Code Review Q#143939, answer score: 10