Memoize my recursive coinSums

Question

I have a basic coinSums recursive function:

function coinSums(total) {      
    var coins = [1, 5, 10, 25];
    var output = [];
    var memo={} <--the only part im sure about :)
    function subroutine(pos, runningSum, currentCombo) {
        if (total === runningSum) {
            return output.push(currentCombo)
        } else if (total < runningSum) {
            return false
        } else
            for (var i = pos; i < coins.length; i++) {
                subroutine(i, runningSum + coins[i], currentCombo.concat(coins[i]))
            }
    }
    subroutine(0, 0, [])
    return output.length; }

I would really like to figure out a way 'memoize' it to improve the O(n^k) runtime (k=num of coins, n=target, right?), but keep it recursive and not change the recursive call as little as possible. (I need to maintain the combo and runningSum bottom up approach).

I know how to do it with the top down approach. Any genius have any ideas?

ps We can change the pos that i in the for loop starts at to 0 to give us the number of ordered combinations. I need to return the unordered combos which is why I want to maintain the running combos.

Answer 1

I am afraid your requirement is impossible to meet unless you want to use memoization for muliple uses of coinSums itself -- in a single application of the former you are calling subroutine with always different argument sets, and the one making them unique is currentCombo, which I believe cannot be "abstracted from" when memoizing, as it's the core of the whole algorithm...

What you can do is to collect this output thing with top-down recursion, which is "nice" for memoization, though that's probably what you already know...

function coinSums(total) {
    /// "cache":
    var _coinSumsMem_ = {};
    var lookupCoins = function(total,pos) {
        return _coinSumsMem_[[total,pos]];
    };
    var memoizeCoins=function(total,pos, coins) {
        _coinSumsMem_[[total,pos]]
            = coins.map(function(xs) {return xs.slice();}); /// a clone!
    };
    /// "computation":
    var coinsAvailable = [1,5,10,20];    
    findAll = function(total, pos) {
        if(total<0 || pos==coinsAvailable.length) return [];
        else if(total==0) return [[]];
        var result = lookupCoins(total,pos);
        if(result == undefined) {
            var oneWaySums = findAll(total-coinsAvailable[pos], pos);
            oneWaySums.map(function(xs) {xs.push(coinsAvailable[pos]);});
            var otherWaySums = findAll(total, pos+1);
            result = oneWaySums.concat(otherWaySums);
            memoizeCoins(total,pos, result);
        }
        return result;
    };
    return findAll(total,0).length; /// or without length...
}