Project Euler Problem #31

HTML

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:<br/>
<br/>
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).<br/>
It is possible to make £2 in the following way:<br/>
<br/>
1£1 + 150p + 220p + 15p + 12p + 31p<br/>
How many different ways can £2 be made using any number of coins?<br/>

JavaScript

//Set up the coin values
var coinValues = [1, 2, 5, 10, 20, 50, 100, 200];

//Set up the object to memoize the operation results
var comboCounts = [];
for(var i = 0; i < coinValues.length; i++){
    comboCounts[i] = [];
}

var findDifferentCoinCombos = function(amount, maxIndex) {
    var combos = 0;

    //Consider the max index if no index was passed in
    maxIndex = (maxIndex || maxIndex == 0) ? maxIndex : coinValues.length - 1;
    
    //Handle 1 combo cases manually
    if(maxIndex == 0 || amount == 0){
        return 1;
    }
    //If we've already figured out the answer, return that
    if(comboCounts[maxIndex][amount]){
        return comboCounts[maxIndex][amount];
    }
    
    //Sum the possible combinations of lesser coins for each possible amount of highest valued coins
    var coinValue = coinValues[maxIndex];
    var coinAmount = 0;
    while(amount >= coinAmount){
        combos += findDifferentCoinCombos(amount - coinAmount, maxIndex - 1);
        coinAmount += coinValue;
    }
    
    //Memoize it
    comboCounts[maxIndex][amount] = combos;

    //Return the answer
    return combos;
};

console.log(findDifferentCoinCombos(200));