# ------------------------------------------------------------------------
#  P A C K   S E L E C T E D   I T E M S   I N T O  A   C O N T A I N E R
# ------------------------------------------------------------------------

# We are given weight of each item in a set of items.
# There is a container with a given weight capacity.
# We have to choose items to fill container completely,
# in other words, the sum of weights of the items in the container
# has to be equal to the container capacity

def pack( items, chosenItems,  iItem, capacity, sumSoFar ):

    # solution found?
    if sumSoFar == capacity:
        print( chosenItems )
        return

    # no more items available?
    if iItem == len( items ):
        return

    # A. try to add another item ...
    currItem = items[iItem]
    if currItem + sumSoFar <= capacity:
        chosenItems.append( currItem )
        pack( items, chosenItems, iItem+1, capacity, sumSoFar+currItem )  # (*)
        chosenItems.pop()   # remove the item after recursion!

    # B. ...or move to the next item skipping the current one
    pack( items, chosenItems, iItem+1, capacity, sumSoFar )


items = [ 11, 21, 32, 83, 5, 3, 1]
pack( items, [], 0, 44, 0 )
print()
pack( items, [], 0, 100, 0 )
print()
items = [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
pack( items, [], 0, 50, 0 )
print()

# ------------------------------------------------------------------------
#     C O I N     C H A N G E
# ------------------------------------------------------------------------

# Express a given total a s sum of coins of given value.
# Each coin value may be used repeatedly.

def coinChange( coins, changeList, iCoin, givenSum, sumSoFar ):
    if sumSoFar == givenSum:
        print( changeList )
        return
    if iCoin == len( coins ):
        return

    # A. try to add another coin of the same value...
    currCoin = coins[iCoin]
    if currCoin + sumSoFar <= givenSum:
        changeList.append( currCoin )
        coinChange( coins, changeList, iCoin, givenSum, sumSoFar+currCoin )  # (*)
        changeList.pop()   # remove the item after recursion!

    # B. ...or move to next coin skipping the current one
    coinChange( coins, changeList, iCoin+1, givenSum, sumSoFar )

# note that the single structural difference between functions
# pack(...) and coinChange(...) is in the first recursive call:
#   pack( items, chosenItems, iItem+1, capacity, sumSoFar+currItem )      # (*)
#   coinChange( coins, changeList, iCoin, givenSum, sumSoFar+currCoin )   # (*)
# The index of item is increased in the first case,
# the index of the coin is NOT increased in the second case.
# Not increasing the index allows the algorithm
# to consider any particular coin value repeatedly

coins = [ 50, 20, 10, 5, 2, 1]
coinChange( coins, [], 0, 14, 0 )
print()