\nToday’s Little Program enumerates all the ways of making\nchange for a particular amount given a set of available denominations.\n<\/p>\n
\nThe algorithm is straightforward.\nTo make change for a specific amount from a set of available\ndenominations,\nyou can take one denomination and decide\nhow many of those you want to use.\nThen use the remaining denominations to make change for the remainder.\n<\/p>\n
\nFor example, if the available coins have values [1, 5, 10, 25]\nand you want to make change for 60 cents, you first decide how many\n25-cent pieces you want to use.\nIf you use none, then you need to make change for 60 cents\nusing just [1, 5, 10].\nIf you use one, then you need to make change for 35 cents\nusing just [1, 5, 10].\nAnd if you use two, then you need to make change for 10 cents\nusing just [1, 5, 10].\n<\/p>\n
\n(We use the largest coin first to reduce the number of dead ends,\nlike asking “Please make change for 83 cents using only 10-cent coins.”)\n<\/p>\n
\nfunction MakeChange(coins, total, f) {\n if (total == 0) { f([]); return; }\n if (coins.length == 0) return;\n var coin = coins[coins.length - 1];\n var remaining = coins.slice(0, -1);\n var used = [];\n for (var target = total; target >= 0; target -= coin) {\n MakeChange(remaining, target, function(s) {\n f(used.concat(s));\n });\n used.push(coin);\n }\n}\nMakeChange([1, 5, 10, 25], 60, console.log.bind(console));\n<\/pre>\n\nFirst, we take care of some base cases.\nTo make change for zero cents, we simply use zero coins.\nAnd it’s not possible to make\nchange for a nonzero amount with no coins.\n<\/p>\n
\nOtherwise, we take the highest denomination coin\nand try using zero of them, then one of them, and so on,\nuntil we exceed the total amount necessary.\n<\/p>\n