coins.py

coins.py

# -*- coding: utf-8 -*-

def product(v, coins=[500, 100, 50, 10, 5, 1], used=[]):
    if len(coins) == 1:
        yield 1
    else:
        for i, coin in enumerate(coins):
            diff = v - coin
            if diff == 0:
                yield 1
            elif diff >= 0:
                for x in product(diff, coins[i:], used + [coin]):
                    yield x

print sum(product(1000))