Subset Sum of Coins for Exact Change
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#=======================================================================
# 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[0] 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] = 0; //base case             : 0 coins for 0 cent
#   N[1] = N[0]+coins[0] = 0+1 = 1    : 1 coin for 1 cent   [1]
#   N[2] = N[1]+coins[0] = 1+1 = 2    : 2 coins for 2 cents [1,1]
#   N[3] = coins[1] = 1               : 1 coin for 3 cents  [3]
#   N[4] = N[1]+coins[1] = 1+1 = 2    : 2 coins for 4 cents [3,1]
#   N[5] = coins[2] = 1               : 1 coin for 5 cents [5]
#   N[6] = N[5]+coins[0] = 1+1 = 2    : 2 coins for 6 cents [5,1]
#   N[7] = N[6]+coins[0] = 2+1 = 3    : 3 coins for 7 cents [5,1,1]
#   N[8] = N[5]+coins[2] = 1+1 = 2    : 2 coins for 8 cents [5,3]
#   N[9] = N[8]+coins[0] = 2+1 = 3    : 3 coins for 9 cents [5,1,3]
#   N[10] = N[5]+coins[2] = 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] = 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[10] is N[5], and the next subtotal
# that takes fewer coins than N[5] is N[0]. Hence the denominations
# for N[10] 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;