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.
See Question&Answers more detail:os