PY
py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Give the change for money using coins
# VcC 2017
# Nb of ways you can give change
nbchange=lambda m,c:sum(nbchange(m-i*c[0],c[1:]) for i in range(m//c[0]+1)) if len(c) else m==0
# All the ways to do exact change
gchange=lambda m,c:([] if m%c[0] else [[c[0]]*(m//c[0])]) if len(c)==1 else list(x+[c[0]]*i if i else x for i in range(m//c[0]+1) for x in gchange(m-c[0]*i,c[1:]))
coins=[50,15,8,7,5]
money=53
print(nbchange(money,coins))
print(gchange(money,coins))
Enter to Rename, Shift+Enter to Preview
OUTPUT
Run