java - Coin change recursive approach

Question

I am trying to solve the coin change problem using a recursive approach. The problem goes like this:

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount.

You are given an amount and an array of coins.

Here is what I have so far:

private static int[] coins = {1,2,5};

public static void main(String[] args) {
    System.out.println(count(13));
}

public static int count(int n)
{
    // If n is 0 then there is 1 solution
    if (n == 0)
        return 1;
     
    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;
 
    return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]);
}

When I do this I get nothing close to the right combinations. The problem I think is with the return but I can not figure out why. Here I am subtracting the coin from the amount and adding them together each time. When it gets 0 it returns 1.

Answer 1

Firstly you should replace:

return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]);

With a loop:

int nCoins = 0;
for(int coin=0; coin<coins.length; coin++)
{
    nCoins += count(n-coins[coin]);
}
return nCoins;

The trouble with this is that it'll generate all permutations of coins (=634). To get each unique combination of coins you need to make sure you start each level of recursion at the current coin. For this you need to add an argument to your count method, to indicate the position in the coin array at which to start.

public static int count(int n, int startCoin)

Your loop then becomes

int nCoins = 0;
for(int coin=startCoin; coin<coins.length; coin++)
{
    nCoins += count(n-coins[coin], coin);
}
return nCoins;

Which gives the correct answer (14).