Skip to content

Instantly share code, notes, and snippets.

@crsanti
Created June 18, 2017 19:50
Show Gist options
  • Select an option

  • Save crsanti/a36a635b14e3d6e5a8b2a1b71db7ec82 to your computer and use it in GitHub Desktop.

Select an option

Save crsanti/a36a635b14e3d6e5a8b2a1b71db7ec82 to your computer and use it in GitHub Desktop.
Coin problem
function makeChange(coins, counts, startIndex, totalAmount) {
if (startIndex >= coins.length) {
let combinations = [];
for (let i = 0; i < coins.length; i++) {
combinations = [...combinations, ...Array(counts[i]).fill(coins[i])];
}
console.log(combinations);
} else if (startIndex === coins.length - 1) {
if (totalAmount % coins[startIndex] === 0) {
counts[startIndex] = totalAmount / coins[startIndex];
makeChange(coins, counts, startIndex + 1, 0);
}
} else {
for (let i = 0; i <= totalAmount / coins[startIndex]; i++) {
counts[startIndex] = i;
makeChange(coins, counts, startIndex + 1, totalAmount - coins[startIndex] * i);
}
}
}
const coins = [1, 2, 3];
const counts = Array(coins.length);
makeChange(coins, counts, 0, 5);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment