Coin Change II : To take a value or not to

Question

The problem goes like this:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

Here's how I thought to take on this problem: On any given index here're three things I can do:

• I take the value of the index and remain at the same index
• I take the value of the index and move on to the next one
• I do not take the value of the index and move on to the next one.

Now obviously I got the answer wrong.

var change = function(amount, coins, index = 0) {
    if(amount === 0) return 1;
    if(index >= coins.length|| amount < 0)  return 0;

    let way1 = change(amount - coins[index], coins, index);
    let way2 = change(amount - coins[index], coins, index+1);
    let way3 = change(amount, coins, index+1);

    return way1 + way2 + way3;

};

console.log(change(3, [1,2,5]))

So I debugged and found the reason. The second step is just adding extra number of ways.

And hence I removed and got the solution accepted.

var change = function(amount, coins, index = 0, memo={}) {
    if((amount+','+index) in memo) return memo[amount+','+index];
    if(amount === 0) return 1;
    if(index >= coins.length|| amount < 0)  return 0;

    let way1 = change(amount - coins[index], coins, index, memo);
    let way2 = change(amount, coins, index+1, memo);

    memo[amount+','+index] = way1 + way2;
    return memo[amount+','+index];

};

console.log(change(5, [1,2,5]))

Now somehow I'm unable to logically think why way2 was un-necessary. After all, it makes logically sense to take the value at that index and still move to the other one. Appreciate thoughts on this.

Answer 1

At any point, there are exactly two things you can do:

1. Use the current denomination.
2. Move on to the next denomination, never using any previous denominations again.

Your original way2 was a combination of both of these two steps at once (use the current denomination once and then move to the next one), so it is always overcounting.

You can also solve this via tabulation:

function change(amount, coins) {
    const ways = Array(amount + 1).fill(0);
    ways[0] = 1;
    for (const coin of coins)
        for (let i = coin; i <= amount; ++i)
            ways[i] += ways[i - coin];
    return ways[amount];
}