How to count possible combination for coin problem

Question

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

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

Solution 4

Aryabhatta’s answer for counting the number of ways to make change with coins of fixed denominations is very cute but also impractical to implement as described. Rather than use complex numbers, we’ll use modular arithmetic, similar to how the number-theoretic transform replaces a Fourier transform for multiplying integer polynomials.

Let D be the least common multiple of the coin denominations. By Dirichlet’s theorem on arithmetic progressions, there exist infinitely many prime numbers p such that D divides p - 1. (With any luck, they’ll even be distributed in a way such that we can find them efficiently.) We’ll compute the number of ways modulo some p satisfying this condition. By obtaining a crude bound somehow (e.g., n + k - 1 choose k - 1 where n is the total and k is the number of denominations), repeating this procedure with several different primes whose product exceeds that bound, and applying the Chinese remainder theorem, we can recover the exact number.

Test candidates 1 + k*D for integers k > 0 until we find a prime p. Let g be a primitive root modulo p (generate candidates at random and apply the standard test). For each denomination d, express the polynomial x**d - 1 modulo p as a product of factors:

x**d - 1 = product from i=0 to d-1 of (x - g**((p-1)*i/d)) [modulo p].

Note that d divides D divides p-1, so the exponent indeed is an integer.

Let m be the sum of denominations. Gather all of the constants g**((p-1)*i/d) as a(0), ..., a(m-1). The next step is to find a partial fraction decomposition A(0), ..., A(m-1) such that

sign / product from j=0 to m-1 of (a(j) - x) =
    sum from j=0 to m-1 of A(j)/(a(j) - x) [modulo p],

where sign is 1 if there are an even number of denominations and -1 if there are an odd number of denominations. Derive a system of linear equations for A(j) by evaluating both sides of the given equation for different values of x, then solve it with Gaussian elimination. Life gets complicated if there are duplicates; it's probably easiest just to pick another prime.

Given this setup, we can compute the number of ways (modulo p, of course) to make change amounting to n as

sum from j=0 to m-1 of A(j) * (1/a(j))**(n+1).

Solution 5

package algorithms;

import java.util.Random;

/**`enter code here`
 * Owner : Ghodrat Naderi
 * E-Mail: [email protected]
 * Date  : 10/12/12
 * Time  : 4:50 PM
 * IDE   : IntelliJ IDEA 11
 */
public class CoinProblem
 {
  public static void main(String[] args)
   {
    int[] coins = {1, 3, 5, 10, 20, 50, 100, 200, 500};

    int amount = new Random().nextInt(10000);
    int coinsCount = 0;
    System.out.println("amount = " + amount);
    int[] numberOfCoins = findNumberOfCoins(coins, amount);
    for (int i = 0; i < numberOfCoins.length; i++)
     {
      if (numberOfCoins[i] > 0)
       {
        System.out.println("coins= " + coins[i] + " Count=" + numberOfCoins[i] + "\n");
        coinsCount += numberOfCoins[i];
       }

     }
    System.out.println("numberOfCoins = " + coinsCount);
   }

  private static int[] findNumberOfCoins(int[] coins, int amount)
   {
    int c = coins.length;
    int[] numberOfCoins = new int[coins.length];
    while (amount > 0)
     {
      c--;
      if (amount >= coins[c])
       {
        int quotient = amount / coins[c];
        amount = amount - coins[c] * quotient;
        numberOfCoins[c] = quotient;
       }

     }
    return numberOfCoins;
   }
 }

View more solutions