# Coin Change
# A few different values of coins are given.
# It is supposed that unlimited number of coins of each value is available.
# Also, a particular monetary value is given.
# The problem is to list all different possibilities
# of expressing the given value as a sum of given coins.
# Example. Coin values = [5, 2, 1], monetary value = 7.
# Possible changes 1. 7 = 5+2
# 2. 7 = 5+1+1
# 3. 7 = 2+2+2+1
# 4. 7 = 2+2+1+1+1
# 5. 7 = 2+1+1+1+1+1
# a single recursive function does the whole job
def change( monValue, maxCoinIndex, noOfUsedCoins ):
global coinsList, changeList, counter
# success
if monValue == 0:
counter += 1
print( str(counter) +'.', changeList[0:noOfUsedCoins] )
return
# add another coin to changeList
for coinIndex in range( maxCoinIndex, len(coinsList) ):
currCoin = coinsList[coinIndex]
newValue = monValue - currCoin
if newValue < 0 : continue
changeList[noOfUsedCoins] = currCoin
change( newValue, coinIndex, noOfUsedCoins+1 )
return
# For simplicity, a single list of used coins is used.
# it is filled with the coins, step by step, by the
# recursive function "change".
# The solution depends on the fact
# that the coins in a list are always kept in decreasing order.
# This arrangement helps us to avoid generating equivalent duplicates
# like e.g. [1,5,1], [1,1,5], [5,1,1] etc.
coinsList = [ 5, 2, 1 ]
value = 7
changeList = [0] * value
counter = 0
change( value, 0, 0 )