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.