coin change

solve.js

function recurSolve(sum, coins) {
  var coins = coins.slice().sort(function (a, b) { return b - a; });
  console.log(coins);
  var go = function (sum, coins) {
    if (sum === 0)  return 1;
    if (coins.length === 0 || sum < 0) return 0;
    return go(sum - coins[0], coins) + go(sum, coins.slice(1));
  };

  return go(sum, coins);
}

function linearSolve(sum, coins) {
  var coins = coins.slice().sort();
  var c1 = new Array(sum + 1);
  var c2 = new Array(sum + 1);

  for (var i = 0; i <= sum; ++i) {
    c1[i] = i % coins[0] === 0 ? 1 : 0;
    c2[i] = 0;
  }

  for (var i = 1, len = coins.length; i < len; ++i) {
    var step = coins[i];
    for (var k = 0; k <= sum; ++k) {
      for (var j = 0; k + j <= sum; j += step) {
        c2[j + k] += c1[k];
      }
    }

    for (var x = 0; x <= sum; ++x) {
      c1[x] = c2[x];
      c2[x] = 0;
    }
  }

  return c1[sum];
}