# Subset Sum: Coin 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   {1}
*   N = N+coins = 1+1 = 2    : 2 coins for 2 cents (1,1)
*   N = coins = 1               : 1 coin for 3 cents  {3}
*   N = N+coins = 1+1 = 2    : 2 coins for 4 cents (3,1)
*   N = coins = 1               : 1 coin for 5 cents {5}
*   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)
********************************************************************/
package algorithm.programming.dynamic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetSum {

/**
* return makeExactChange(numberOfCoinsPerSubtotal(t, coins), t);
**/
public List<Integer> subsetSumOfCoins(int[] coins, int t) {
int[] C = numberOfCoinsPerSubtotal(t, coins);
return makeExactChange(C, t);
}

/**
* Compute the number of coins in each subtotal amount of money
* from 0 to t.
*/
private int[] numberOfCoinsPerSubtotal(int t, int[] coins) {
int[] C = new int[t + 1];
Arrays.fill(C, Integer.MAX_VALUE);
C = 0;// base case
for (int coin : coins) {
for (int subtotal = 1; subtotal <= t; subtotal++) {
if (coin <= subtotal && 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}.
**/
private List<Integer> makeExactChange(int[] C, int t) {
List<Integer> result = new ArrayList<Integer>();
while (0 < C[t]) {
int big = t;
while (C[big] <= C[--t]);
}
return result;
}
}
```
```package algorithm.programming.dynamic;

import java.util.Arrays;
import java.util.List;
import static org.junit.Assert.*;
import org.junit.Test;

public class SubsetSumTest {

/**
* Test of subsetSumOfCoins method, of class SumOfCoins.
*/
@Test
public void testSubsetSumOfCoins() {
System.out.println("subsetSumOfCoins");
int[] coin = {1, 5, 10, 25};
int t = 167;
SubsetSum instance = new SubsetSum();
List expResult = Arrays.asList(1, 1, 5, 10, 25, 25, 25, 25, 25, 25);
List result = instance.subsetSumOfCoins(coin, t);
assertEquals(expResult, result);
}
}```