How to count possible combination for coin problem

I am trying to implement a coin problem, Problem specification is like this

Create a function to count all possible combination of coins which can be used for given amount.

All possible combinations for given amount=15, coin types=1 6 7 
1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2) 1,1,1,1,1,1,1,1,1,6,
3) 1,1,1,1,1,1,1,1,7,
4) 1,1,1,6,6,
5) 1,1,6,7,
6) 1,7,7,

function prototype:

int findCombinationsCount(int amount, int coins[])

assume that coin array is sorted. for above example this function should return 6.

Anyone guide me how to implement this??

Solution 1:

Use recursion.

int findCombinationsCount(int amount, int coins[]) {
    return findCombinationsCount(amount, coins, 0);
}

int findCombinationsCount(int amount, int coins[], int checkFromIndex) {
    if (amount == 0)
        return 1;
    else if (amount < 0 || coins.length == checkFromIndex)
        return 0;
    else {
        int withFirstCoin = findCombinationsCount(amount-coins[checkFromIndex], coins, checkFromIndex);
        int withoutFirstCoin = findCombinationsCount(amount, coins, checkFromIndex+1);
        return withFirstCoin + withoutFirstCoin;
    }
}

You should check this implementation though. I don't have a Java IDE here, and I'm a little rusty, so it may have some errors.

Solution 2:

Although recursion can work and is often an assignment to implement in some college level courses on Algorithms & Data Structures, I believe the "dynamic programming" implementation is more efficient.

public static int findCombinationsCount(int sum, int vals[]) {
        if (sum < 0) {
            return 0;
        }
        if (vals == null || vals.length == 0) {
            return 0;
        }

        int dp[] = new int[sum + 1];
        dp[0] = 1;
        for (int i = 0; i < vals.length; ++i) {
            for (int j = vals[i]; j <= sum; ++j) {
                dp[j] += dp[j - vals[i]];
            }
        }
        return dp[sum];
    }

Solution 3:

You can use generating function methods to give fast algorithms, which use complex numbers.

Given the coin values c1, c2, .., ck, to get the number of ways to sum n, what you need is the coefficient of x^n in

(1 + x^c1 + x^(2c1) + x^(3c1) + ...)(1+x^c2 + x^(2c2) + x^(3c2) + ...)....(1+x^ck + x^(2ck) + x^(3ck) + ...)

Which is the same as finding the coefficient of x^n in

1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck)

Now using complex numbers, x^a - 1 = (x-w1)(x-w2)...(x-wa) where w1, w2 etc are the complex roots of unity.

So

1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck)

can be written as

1/(x-a1)(x-a2)....(x-am)

which can be rewritten using partial fractions are

A1/(x-a1) + A2/(x-a2) + ... + Am/(x-am)

The coefficient of x^n in this can be easily found:

A1/(a1)^(n+1) + A2/(a2)^(n+1) + ...+ Am/(am)^(n+1).

A computer program should easily be able to find Ai and ai (which could be complex numbers). Of course, this might involve floating point computations.

For large n, this will be probably faster than enumerating all the possible combinations.

Hope that helps.

Solution 4:

Very simple with recursion:

 def countChange(money: Int, coins: List[Int]): Int = {
    def reduce(money: Int, coins: List[Int], accCounter: Int): Int = {
        if(money == 0) accCounter + 1
        else if(money < 0 || coins.isEmpty) accCounter
        else reduce(money - coins.head, coins, accCounter) + reduce(money, coins.tail, accCounter)
   }

   if(money <= 0 || coins.isEmpty) 0
   else reduce(money, coins, 0)
}

This is example in SCALA