Recursive function to find the number of ways a number can be generated out of a set of numbers

Question

I had a job interview test and the question I got was about making a function which would return the number of ways a number could be generated by adding numbers from a certain set, where any number in the set can be used N times.

It is like if I have the number 10 and I want to find out how many ways 10 can be generated using [2,3,5]

1. 2+2+2+2+2 = 10
2. 5+3+2 = 10
3. 2+2+3+3 = 10
4. 5+5 = 10

to solve it I made this function:

function getNumberOfWays($money, $coins) {
    static $level = 0;
    if (!$level) {
        sort($coins);
    }

    if ($level && !$money) {
        return 1;
    } elseif (!$level && !$money) {
        return 0;
    }

    if ($money === 1 && array_search(1, $coins) !== false) {
        return 1;
    } elseif ($money === 1 && array_search(1, $coins) === false) {
        return 0;
    }

    $r = 0;
    $tmpCoins = $coins;
    foreach ($coins as $index => $coin) {
        if (!$coin || $coin > $money) {
            continue;
        }

        $tmpCoins[$index] = 0;
        $tmpMoney = $money;
        do {
            $tmpMoney -= $coin;
            if ($tmpMoney >= 0) {
                $level++;
                $r += getNumberOfWays($tmpMoney, $tmpCoins);
                $level--;
            } elseif (!$tmpMoney) {
                $r++;
            }
        } while ($tmpMoney >= 0);
    }

    return $r;
}

This function works correctly: it returns the right value.

Can I improve it in any way?

Answer 1

I'm assuming in this answer that you have infinite quantities of the designated numbers at your disposal, since that appears to be the way your code works. With that condition, this problem is the coin sums problem on Project Euler: given a set of coin denominations, how many ways can change be made for a number?

Looking at your code in terms of efficiency, the top-down recursive function is doing a lot of repeated work because of overlapping subproblems, similar to the recursive Fibonacci problem and is the hallmark of dynamic programming.

The biggest improvement available to you is using a memo or cache in the form of an associative array. Memoization makes it possible to keep track of what's already been computed for a given recursive call and avoid recomputations, pruning off huge chunks of the call tree. This effectively turns the exponential O(n^k) problem into O(nk) [source] where k is the number of coins.

There's also a bottom-up iterative version which is an improvement still over the "recursion with cache" version. I recommend adding a cache to your algorithm as above, solving the Project Euler problem and spending some time perusing the solution thread that you'll gain access to which contains many imaginative and efficient solutions including these bottom-up versions.

In terms of coding style, there are variables and loops that can be removed. Moving "set up" code out of the recursive call and into a wrapper can save a few conditional checks and eliminate the level variable. Doing an array_search through your coins array and setting used elements to 0 is a bit awkward and can be handled easily by passing an index variable to determine which coins have been used already. The full function header I used has 4 parameters (including the index and a reference to the memo), which makes it nice to wrap.

Lastly, your base case checks need only happen for being out of money. When that happens, either you've made change successfully, or the change you tried to make wasn't valid (you went into negative numbers). No need to test anything else. All told, the whole program can be 30 lines or less.

I'd like to post my PHP code here, but in the spirit of Project Euler, you'll have the most fun if you solve it yourself instead of reading a spoiler! We can compare notes afterwards if you want (although the solutions you'll see in the forum will be far superior).