# 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 )