# Subset Sum of Coins for Exact Changeby Isai Damier, Android Engineer @ Google

```#=======================================================================
# Author: Isai Damier
# Title: Subset Sum of Coins for Exact Change
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#   Given a set of coins, find the shortest sequence of coins that
#   adds up to a given total t.
#
# Time Complexity: O(n*t)
#    where n is the number of coins and t is the total to make change for.
#
# Sample Input: coin=[1,5,10,25]; t=167
# Sample Output: [1, 1, 5, 10, 25, 25, 25, 25, 25, 25]
#
# Dynamic Programming Strategy:
#
#   Our approach is to compute the number of coins in each subtotal
#   amount of money from 0 to t, inclusive. The technique is to
#   add coins to a previously found subtotal so to get the next
#   subtotal, until we solve for the minimum number of coins in t.
#   After that, we simply walk the list of subtotals to get the
#   exact change (you'll see).
#
# 0] Create an array N of size t+1:
#     The indices/keys of the array represent different subtotals.
#     And the element/value at each index represents the number of
#     coins that adds up to that given subtotal:
#     N[subtotal] = number of coins
# 1] Initialize N to infinity:
#     Before any computation is performed, assume/pretend that each
#     subtotal takes an infinite number of coins to compute. We know
#     that's not true, but that's what we have to prove.
# 2] Set N at index 0 to 0:
#     Recall that for the N array, each index represents a subtotal
#     and the element at that index represents the number of coins
#     that add up to that subtotal. Therefore, we can set N to 0
#     because we know for certain that it takes 0 coins to get 0
#     amount of money (this is the anchor/base case).
#
# 3] For subtotals ranging from 1 to t, inclusive, do:
#     For each coin:
#       If coin <= subtotal and N[subtotal-coin]+1 < subtotal, then:
#         N[subtotal] = N[subtotal-coin]+1
#
#   Step 3 is known as the relaxation step. We started with an extreme
#   and unrealistic assumption (i.e. that it takes infinite number of
#   coins to make change for the money t), then we keep relaxing
#   our assumptions until we get to the truth.
#
# EXAMPLE: You should really skip the following manual example and go
#   straight to the code. Then, if you need help seeing how the code
#   is computing the number of coins for each subtotal, come back here.
#
#   For t=10 and coins = [1,3,5], the final version of N is:
#
#   N = 0; //base case             : 0 coins for 0 cent
#   N = N+coins = 0+1 = 1    : 1 coin for 1 cent   
#   N = N+coins = 1+1 = 2    : 2 coins for 2 cents [1,1]
#   N = coins = 1               : 1 coin for 3 cents  
#   N = N+coins = 1+1 = 2    : 2 coins for 4 cents [3,1]
#   N = coins = 1               : 1 coin for 5 cents 
#   N = N+coins = 1+1 = 2    : 2 coins for 6 cents [5,1]
#   N = N+coins = 2+1 = 3    : 3 coins for 7 cents [5,1,1]
#   N = N+coins = 1+1 = 2    : 2 coins for 8 cents [5,3]
#   N = N+coins = 2+1 = 3    : 3 coins for 9 cents [5,1,3]
#   N = N+coins = 1+1 = 2   : 2 coins for 10 cents [5,5]
#=======================================================================

# return makeExactChange(numberOfCoinsPerSubtotal(t, coins), t);
def subsetSumOfCoins( coins, t ) :
C = numberOfCoinsPerSubtotal( t, coins )
return makeExactChange( C, t )

#======================================================================
# Compute the number of coins in each subtotal amount of money
# from 0 to t.
#======================================================================
from sys import maxint
def numberOfCoinsPerSubtotal( t, coins ):
C = [maxint] * ( t + 1 )
C = 0 # base case
for coin in coins:
for subtotal in range( 1, t + 1 ):
if coin <= subtotal and C[subtotal] > C[subtotal - coin] + 1:
C[subtotal] = C[subtotal - coin] + 1
return C

#======================================================================
# Now that we know how many coins it takes to get each subtotal
# amount of money up to t, we can track the denomination of each coin:
# keep subtracting the next subtotal that takes fewer coins than t.
# For instance in the manual example above where t=10 and
# coins = [1,3,5]; since t N[t=10] takes 2 coins, the next subtotal
# that takes fewer coins than N is N, and the next subtotal
# that takes fewer coins than N is N. Hence the denominations
# for N are 10-5 and 5-0: [5,5].
#======================================================================
def makeExactChange( C, t ):
result = []
while 0 < C[t]:
big = t
while C[big] <= C[t]:
t -= 1
result.append( big - t )

return result;
```
```import unittest
from dynamic_programming import SubsetSum as algorithm

class Test( unittest.TestCase ):

def testSubsetSumOfCoins( self ):
coin = [1, 5, 10, 25]
t = 167
expResult = [1, 1, 5, 10, 25, 25, 25, 25, 25, 25]
result = algorithm.subsetSumOfCoins( coin, t )
self.assertEquals( expResult, result )
```