Instantly share code, notes, and snippets.

# gitchandu/coin-amount.js Created Sep 27, 2012

What would you like to do?
js :: knapsack problem subset (coin problem)
 (function (amount, coins) { 'use strict'; var n = coins.length, cc = function cc(aMoney, aCoins, arr) { var tempArr; if (aMoney < 0 || aCoins.length === 0) { return 0; } else if (aMoney === 0) { console.log(arr); return 1; } else { tempArr = arr.slice(0); tempArr.push(aCoins[0]); return cc(aMoney - aCoins[0], aCoins, tempArr) + cc(aMoney, aCoins.slice(1), arr); } }; console.log(cc(amount, coins, [])); }(10, [5, 1, 2]));
 (function (amount, coins) { 'use strict'; var n = coins.length, sum = function (arr) { return arr.reduce(function (previousValue, currentValue, index, array) { return previousValue + currentValue; }, 0); }, count = function count(target, arr) { var i, temp = 0, tempArr; if (target < 0) { return 0; } else if (target === 0) { console.log(arr + ' = ' + sum(arr)); return 1; } for (i = 0; i < n; i += 1) { tempArr = arr.slice(0); tempArr.push(coins[i]); temp += count(target - coins[i], tempArr); } return temp; }; console.log(count(amount, [])); }(10, [1, 2, 5]));