Subset Sum: Coin Exact Change
by Isai Damier

/*********************************************************************
 * 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)
 ********************************************************************/ 
 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] = 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[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}.
   **/
  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]);
      result.add(big - 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);
  }
}
Puzz! Turn your photo into a puzzle!