CoinChange.js

/**
 * Coin Change Problem
 * ===================
 * Find the number of ways of making changes for a particular amount of cents, N,
 * using a given set of denominations S = {S1,S2,S3,...S[m]}.
 *
 * Let's look into a similiar but simplier case:
 *      | 0  1  2  3  4  5  ... N
 *   ---+--------------------------
 *    1 | 1  1  1  1  1  1
 *    2 | 1  1  2  2  3  3 < (1)
 *    3 | 1  1  2  3  4  5
 *    . |       ^        ^ How do you get this number?
 *    . |      (2)         It is the sum of (1) and (2), why?
 *  S[m]|
 *
 * Let's simplify the problem, what if there's only one denomination, 1?
 *      | 0  1  2  3  4  5  ... N
 *   ---+--------------------------
 *    1 | 1  1  1  1  1  1
 *                       ^ Yay, easy understanding.
 *
 * And let's take 2 into account and find out the result step by step.
 *      | 0  1  2  3  4  5  ... N
 *   ---+--------------------------
 *    1 | 1  1  1  1  1  1
 *      |       -
 *    2 | 1  1  2
 *        -     ^ 2 = 2 + 0; The solutions is partitioned into two sets:
 *                The first set is to find out the ways of making 2 dollar using 1
 *                denomination dollar;
 *                The second set is to find out the ways of making 0 dollar using
 *                only 2 denomination dollar;
 *                And you'll also find out there's no ways of making 1 dollar by
 *                using only 2 denomination dollar. So you can get the result from
 *                the previous row.
 *
 *      | 0  1  2  3  4  5  ... N
 *   ---+--------------------------
 *    1 | 1  1  1  1  1  1
 *      |          -
 *    2 | 1  1  2  2
 *           -     ^ Vice versa.
 *
 * Reasoning
 * ---------
 * The solutions can be partitioned into two sets:
 * 1) There are those sets that do not contain any S[m].
 * 2) Those sets that contain at least one S[m].
 *
 * Conclustion
 * -----------
 * C(N, m - 1) + C(N - S[m], m)
 *
 * Reference
 * ---------
 * - http://www.algorithmist.com/index.php/Coin_Change
 * - https://www.youtube.com/watch?v=_fgjrs570YE
 *
 * Example
 * -------
 * If your country only has 2, 3, 7 denominations in dollars, write a
 * function taking an amount of dollars and compute the possible ways of the dollars
 * combination.
 *
 *      | 0  1  2  3  4  5  6  7  8  9 ... N
 *   ---+-------------------------------------
 *    2 | 1  0  1  0  1  0  1  0  1  0
 *    3 | 1  0  1  1  1  1  2  1  2  2
 *    7 | 1  0  1  1  1  1  2  2  2  3
 */

function CoinChange(N, S) {
  var sortedS = S.sort();
  var ln = S.length;

  if (N < 0 || ln === 0) {
    return 0;
  } else if (N === 0) {
    return 1;
  } else {
    var last = ln - 1;
    return CoinChange(N, sortedS.slice(0, last)) + CoinChange(N - sortedS[last], sortedS);
  }
}

var denominations = [2, 3, 7];
console.log('denominations=', denominations);
console.log('----- test -----');
[1, 14, 128, 153].forEach(function(N) {
  console.log('input %s => output %s', N, CoinChange(N, denominations));
});