In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many different ways can £2 be made using any number of coins?



In [1]:

    
import math
coin_denoms = [1,2,5,10,20,50,100,200]

def num_ways(val, denoms):
    if len(denoms) == 0:
        return 0
    
    if val == 0:
        return 1
    
    # Find highest
    m = -1
    for i,v in enumerate(denoms):
        m = i
        if v > val:
            #print v,">",val
            break
    M = denoms[m]
    #print "val:", val, "denoms:", denoms, "max denom:", M
    
    count = 0
    for j in range(int(math.floor(val*1.0/M)) + 1):
        if val - j*M == 0:
            #print val,'-',j,'*',M,'= 0'
            count += 1
        else:
            #print "recursing to express ",val - j*M, "using", denoms[:m]
            count += num_ways(val - j*M, denoms[:m])
    #print "Count:",count
    
    return count

assert num_ways(val=5, denoms=coin_denoms) == 4
assert num_ways(val=6, denoms=coin_denoms) == 5

num_ways(val=200, denoms=coin_denoms)









    Out[1]:





73682