Total number of ways to count the possible combination for coin

Question

Possible Duplicate:
How to count possible combination for coin problem

In this case suppose the amount is 15 and coins are 1, 6, 7 then total number of ways to it is 6. Below code works fine but its not that much efficient. Any suggestions will be appreciated.

public class CoinProblem {

    public static void main(String[] args) {
        int amount = 15;
        int coinTypes[] = {1,6,7};


        int combinations = 0;
        for (int i = 0; i * 7 <=15; i++) {
            for (int j = 0; j * 6 + i * 7 <= 15; j++) {
              combinations++;
            }
        }
        System.out.println(combinations);


    }
}

Well my first suggestion is that if you're going to use an array to store `coinTypes` that you... actually use the array in your calculation somewhere... — corsiKa, Dec 05 '11 at 03:30
Whoever's giving you this homework must be reusing their questions, [this question](http://stackoverflow.com/questions/4243831/how-to-count-possible-combination-for-coin-problem) is identical to yours, with an amount of 15 and coins of 1, 6, 7. And it's in Java. There's also [this](http://stackoverflow.com/questions/1106929/find-all-combinations-of-coins-when-given-some-dollar-value) and [this](http://stackoverflow.com/questions/5897184/algorithm-to-determine-coin-combinations). — AusCBloke, Dec 05 '11 at 03:56

score 0 · Answer 1 · answered Dec 05 '11 at 03:54

If you are looking for a dynamic programming solution (that can work if you have a larger number of coins and a larger total sum), one idea that I have is:

int[] ways = new int[amount+1];
ways[0] = 1;    //There is only one way to have 0 money, no coins
for (int coin : coinTypes)
{
    for (int i = 1; i <= amount; i++)
    {
        ways[i] += ways[i-coin];
    }
}

Standard disclaimer, I did not run this code. It may have bugs, but it does look like it will work. It has at least two: 1. You need to initialize the ways array to 0. 2. You need to guard against array underflows (taking array indexes less than 0).

The way that it works is that you store how many ways you can get every total count using only one type of coin, then two types of coin, and finally all three. For each amount y, you know that you can achieve that amount with a coin of value x by looking all the ways that you can get a value of y-x and then adding a coin of value x.

Total number of ways to count the possible combination for coin

1 Answers1