How to count possible combination for coin problem

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.

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.

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];
    }