Coin change recursive approach

Viewed 14325

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.

4 Answers
Related