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).

Answer 2

There are solutions to this problem already posted, so I'll assume you're asking about how to think about it, not for the answer itself.

Try this:

Let V be the target value.

Let C[i] be the i'th coin value.

Recursive solutions are about making a choice that reduces the size of problem, then recursively using the same solution on the smaller problem.

When the problem is small enough to solve easily without recurring, we just return that solution. This is the "base case."

Here the choice is to use a specific number N[i] of coins with value C[i].

We need to to this for all possible values of N[i], i.e. N[i] = 0,1,2,...floor(V/C[i]). The integer floor(V/C[i]) is just the maximum number of i'th coins that might produce correct change.

Once we've made a choice of how many i'th coins to use, we shouldn't change that decision. (This is where your solution goes wrong.) The simplest way to do this is to exploit the implicit order of coins due to their array indices. We recursively find the number of ways to make change using coins i+1 and larger for the remaining part of the target value: V - N[i] * coins[i].

(An alternative design would be to maintain the coins in a set and make the choice by removing coin[i] from the set before recurring. But let's stay with the indices because the resulting code is simpler.)

To produce the result, we just add up all the recursively determined counts.

With that thinking, we can choose a signature for the recursive method:

/** 
 * Return the number of ways to make change for the given value 
 * using coins i >= iMin.
 */
int count(int value, int iMin);

Time to think about bases cases. "Success" is when value is exactly zero: we can make change in exactly 1 way by doing exactly nothing! "Failure" occurs when value isn't zero, and we're out of coin values to try. This is just when iMin has reached the length of the coins array.

Let's put this thinking into code:

int count(int value, int iMin) {
  if (value == 0) return 1;  // Success base case.
  if (iMin >= coins.length) return 0; // Failure base case.
  result = 0;
  for (int ni = 0; ni <= value / coins[iMin]; ++ni)
    result += count(value - ni * coins[iMin], iMin + 1);
  return result;
}

To start the recursion, just use the target value and iMin of zero:

int result = count(target, 0);

Note that though this solution is correct, it isn't so efficient. Let's leave that discussion for another day.

Answer 3

According to your algorithm, penny then nickel is treated as a different solution from nickel then penny. You should enforce a particular order. (This is known in mathematics as the difference between permutations and combinations.)

I would consider adding a coin denomination list as a second argument for the recursive function. Then, at each step (other than a terminal step), you will consider two possibilities:

A) consider the possibility of adding another coin, but only one of the denomination at the front of the list

B) consider the possibilty of a recursive call wherein you are truncating the first element off of the list

Answer 4

I do not have enough reputation to comment yet, and am currently working on a solution to your problem. Here is one flaw I noticed in your current code: you are tracking "unique permutations" (I do not know what the official mathematical name would be) rather than "similar permutations," as I believe you would like to.

For example, if you wanted to find count(5), you would get the following nine (9) possible permutations/ ways to arrive at 5:

[2,2,1], [2,1,2], [1,2,2],[5],[2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2], and [1,1,1,1,1].

While I believe you would only want to return four (4) for the following permutations:

[1,1,1,1,1], [2,1,1], [2,2,1], [5]

Here are links that I think further answer your question. Please search through Stack Overflow before asking questions in the future!

How to count possible combination for coin problem

How to find all combinations of coins when given some dollar value