Coin sums

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?

Idea

A problem can be split into smaller problem.

Take a certain coin into consideration, and recursively 'coint sums' the remaining money.

In [1]:
coins = [1, 2, 5, 10, 20, 50, 100, 200]
In [2]:
def solve(s, min_coin=0):
    if s < 0:
        return 0
    elif s == 0:
        return 1
    ways_cnt = 0
    for c in filter(lambda coin: min_coin <= coin <= s, coins):
        ways_cnt += solve(s - c, c)
    return ways_cnt
In [3]:
solve(1)
Out[3]:
1
In [4]:
solve(2)
Out[4]:
2
In [5]:
solve(3)
Out[5]:
2
In [6]:
solve(4)
Out[6]:
3
In [7]:
solve(200)
Out[7]:
73682