Skip to content

Instantly share code, notes, and snippets.

@derek
Last active February 10, 2019 14:31
Show Gist options
  • Save derek/8073844 to your computer and use it in GitHub Desktop.
Save derek/8073844 to your computer and use it in GitHub Desktop.
Change making algorithm in JavaScript - http://en.wikipedia.org/wiki/Change-making_problem
function makeChange (total, coins) {
var tail = coins.slice(0), // clone coins, because we're about to modify it
head = tail.shift(); // grab the first coin out of the purse
// If total is less than zero, or there are no coins left, this isn't a match
if (total < 0 || !head) {
return 0;
}
// If the total reached 0, this is a match
else if (total === 0 ) {
return 1;
}
// Otherwise, branch
else {
// The first branch sends the total and a subset of `coins`
// The second branch send a reduced total, and all the `coins`
return makeChange(total, tail) + makeChange(total-head, coins);
}
}
console.log(makeChange(100, [25, 10, 5, 1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment