Solve the "Coin Change" coding challenge https://www.hackerrank.com/contests/programming-interview-questions/challenges/coin-change

coins.js

#!/usr/bin/env node

// Solve the "Coin Change" problem using a bottom-up dynamic programming
// approach. The time complexity is O(n * coins.length) since we have a nested
// loop. The storage complexity is the same, as we store a matrix.
//
// * `coins` is an array of the coin values, eg. [ 1, 2, 3 ]. We assume it
//   to be non-empty.
// * `n` is the amount, eg. 4 cents.
//
// The top-down solution is also possible (memoization), but can causes
// stack-overflows for large inputs.
//
function findPermutations(coins, n) {

    // The 2-dimension buffer will contain answers to this question:
    // "how much permutations is there for an amount of `i` cents, and `j`
    // remaining coins?" eg. `buffer[10][2]` will tell us how many permutations
    // there are when giving back 10 cents using only the first two coin types
    // [ 1, 2 ].
    var buffer = new Array(n + 1);
    for (var i = 0; i <= n; ++i)
        buffer[i] = new Array(coins.length + 1);

    // For all the cases where we need to give back 0 cents, there's exactly
    // 1 permutation: the empty set. Note that buffer[0][0] won't ever be
    // needed.
    for (var j = 1; j <= coins.length; ++j)
        buffer[0][j] = 1;

    // We process each case: 1 cent, 2 cent, etc. up to `n` cents, included.
    for (i = 1; i <= n; ++i) {

        // No more coins? No permutation is possible to attain `i` cents.
        buffer[i][0] = 0;

        // Now we consider the cases when we have J coin types available.
        for (j = 1; j <= coins.length; ++j) {

            // First, we take into account all the known permutations possible
            // _without_ using the J-th coin (actually computed at the previous
            // loop step).
            var value = buffer[i][j - 1];

            // Then, we add all the permutations possible by consuming the J-th
            // coin itself, if we can.
            if (coins[j - 1] <= i)
                value += buffer[i - coins[j - 1]][j];

            // We now know the answer for this specific case.
            buffer[i][j] = value;
        }
    }

    // Return the bottom-right answer, the one we were looking for in the
    // first place.
    return buffer[n][coins.length];
}

// The boring stuff: parsing and printing.
//
function processData(input) {
    var lines = input.split('\n');
    var coins = lines[0].split(',').map(function (s) {return +s;});
    var n = +lines[1];
    var res = findPermutations(coins, n);
    console.log(res);
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Thanks for documenting your solution. The comments are very helpful. Do you mean "combination" instead of "permutation"?

Thanks!

There is much shorter solution that uses recursion

function count(coins, sum, numCoins) {
	if (numCoins === undefined) {numCoins = coins.length;}
	if (sum == 0) {return 1;}
	if (sum < 0) {return 0;}
	if (numCoins <= 0 && sum > 0) {return 0;}
	return count(coins, sum, numCoins - 1) + count(coins, sum - coins[numCoins - 1], numCoins);
}

console.log(count([1,2,3], 4));

Same solution in C#

    public static long findPermutations(int n, List<long>  c)
    {

        // The 2-dimension buffer will contain answers to this question:
        // "how much permutations is there for an amount of `i` cents, and `j`
        // remaining coins?" eg. `buffer[10][2]` will tell us how many permutations
        // there are when giving back 10 cents using only the first two coin types
        // [ 1, 2 ].
        long[][] buffer = new long[n + 1][];
        for (var i = 0; i <= n; ++i)
            buffer[i] = new long[c.Count + 1];

        // For all the cases where we need to give back 0 cents, there's exactly
        // 1 permutation: the empty set. Note that buffer[0][0] won't ever be
        // needed.
        for (var j = 1; j <= c.Count; ++j)
            buffer[0][j] = 1;

        // We process each case: 1 cent, 2 cent, etc. up to `n` cents, included.
        for (int i = 1; i <= n; ++i)
        {

            // No more coins? No permutation is possible to attain `i` cents.
            buffer[i][0] = 0;

            // Now we consider the cases when we have J coin types available.
            for (int j = 1; j <= c.Count; ++j)
            {

                // First, we take into account all the known permutations possible
                // _without_ using the J-th coin (actually computed at the previous
                // loop step).
                var value = buffer[i][j - 1];

                // Then, we add all the permutations possible by consuming the J-th
                // coin itself, if we can.
                if (c[j - 1] <= i)
                    value += buffer[i - c[j - 1]][j];

                // We now know the answer for this specific case.
                buffer[i][j] = value;
            }
        }

        // Return the bottom-right answer, the one we were looking for in the
        // first place.
        return buffer[n][c.Count];
    }