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开发者_StackOverflow,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??

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

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.

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

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

The recursive solutions mentioned will work, but they're going to be horrendously slow if you add more coin denominations and/or increase the target value significantly.

What you need to speed it up is to implement a dynamic programming solution. Have a look at the knapsack problem. You can adapt the DP solution mentioned there to solve your problem by keeping a count of the number of ways a total can be reached rather than the minimum number of coins required.

package algorithms;

import java.util.Random;

/**`enter code here`
 * Owner : Ghodrat Naderi
 * E-Mail: Naderi.ghodrat@gmail.com
 * 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;
   }
 }

A recursive solution might be the right answer here:

int findCombinationsCount(int amount, int coins[])
{
    // I am assuming amount >= 0, coins.length > 0 and all elements of coins > 0.
    if (coins.length == 1)
    {
        return amount % coins[0] == 0 ? 1 : 0;
    }
    else
    {
        int total = 0;
        int[] subCoins = arrayOfCoinsExceptTheFirstOne(coins);
        for (int i = 0 ; i * coins[0] <= amount ; ++i)
        {
            total += findCombinationsCount(amount - i * coins[0], subCoins);
        }
        return total;
    }
}

Warning: I haven't tested or even compiled the above.

The solution provided by @Jordi is nice but runs extremely slow. You can try input 600 to that solution and see how slow it is.

My idea is to use bottom-up dynamic programming.

Note that generally, the possible combination for money=m and coins{a,b,c} equals combination for

• m-c and coins{a,b,c} (with coin c)
• combination for m and coins{a,b} (without coin c).

If no coins are available or available coins can not cover the required amount of money, it should fill in 0 to the block accordingly. If the amount of money is 0, it should fill in 1.

public static void main(String[] args){
    int[] coins = new int[]{1,2,3,4,5};
    int money = 600;
    int[][] recorder = new int[money+1][coins.length];
    for(int k=0;k<coins.length;k++){
        recorder[0][k] = 1;
    }
    for(int i=1;i<=money;i++){
        //System.out.println("working on money="+i);
        int with = 0;
        int without = 0;

        for(int coin_index=0;coin_index<coins.length;coin_index++){
            //System.out.println("working on coin until "+coins[coin_index]);
            if(i-coins[coin_index]<0){
                with = 0;
            }else{
                with = recorder[i-coins[coin_index]][coin_index];
            }
            //System.out.println("with="+with);
            if(coin_index-1<0){
                without = 0;
            }else{
                without = recorder[i][coin_index-1];
            }
            //System.out.println("without="+without);
            //System.out.println("result="+(without+with));
            recorder[i][coin_index] =  with+without;
        }
    }
    System.out.print(recorder[money][coins.length-1]);

}

This code is based on the solution provided by JeremyP which is working perfect and I just enhanced it to optimize the performance by using dynamic programming.I couldn't comment on the JeremyP post because I don't have enough reputation :)

public static long makeChange(int[] coins, int money) {
    Long[][] resultMap = new Long[coins.length][money+1];
    return getChange(coins,money,0,resultMap);
}

public static long getChange(int[] coins, int money, int index,Long[][] resultMap) {
    if (index == coins.length -1) // if we are at the end      
        return money%coins[index]==0? 1:0;
    else{
        //System.out.printf("Checking index %d and money %d ",index,money);
        Long storedResult =resultMap[index][money];
        if(storedResult != null)
            return storedResult;
        long total=0;
        for(int coff=0; coff * coins[index] <=money; coff ++){

             total += getChange(coins, money - coff*coins[index],index +1,resultMap);
        }
        resultMap[index][money] = total;
        return total;

    }
}

First idea:

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

(the '<=' is superfluous in this case, but is needed for a more general solution, if you decide to change your parameters)

Below is recursion with memoization java solution. for below one we have 1,2,3,5 as coins and 200 as the target amount.

countCombinations(200,new int[]{5,2,3,1} , 0, 0,new Integer[6][200+5]);

static int countCombinations(Integer targetAmount, int[] V,int currentAmount, int coin, Integer[][] memory){

    //Comment below if block if you want to see the perf difference
    if(memory[coin][currentAmount] != null){
        return memory[coin][currentAmount];
    }

    if(currentAmount > targetAmount){
        memory[coin][currentAmount] = 0;
        return 0;
    }
    if(currentAmount == targetAmount){
        return 1;
    }      
    int count = 0;
    for(int selectedCoin : V){
        if(selectedCoin >= coin){                
            count += countCombinations(targetAmount, V, currentAmount+selectedCoin, selectedCoin,memory);
        }
    }        
    memory[coin][currentAmount] = count;        
    return count;
}

#include<iostream>
using namespace std;

int solns = 0;

void countComb(int* arr, int low, int high, int Val)
{
    bool b = false;
    for (size_t i = low; i <= high; i++)
    {
        if (Val - arr[i] == 0)
        {
            solns++;
            break;
        }
        else if (Val - arr[i] > 0)
            countComb(arr, i, high, Val - arr[i]);
        
    }
}

int main()
{
    int coins[] = { 1,2,5 };
    int value = 7;
    int arrSize = sizeof(coins) / sizeof(int);
    countComb(coins,0, arrSize,value);
    cout << solns << endl;
    return 0;
}

Again using recursion a tested solution, though probably not the most elegant code. (note it returns the number of each coin to use rather than repeating the actual coin ammount n times).

public class CoinPerm {

    
    @Test
    public void QuickTest() throws Exception
    {
        int ammount = 15;
        int coins[] = {1,6,7};
        
        ArrayList<solution> solutionList = SolvePerms(ammount, coins);
        
        for (solution sol : solutionList)
        {
            System.out.println(sol);
        }
        
        assertTrue("Wrong number of solutions " + solutionList.size(),solutionList.size()  == 6);
    }

    
    
    public ArrayList<solution>  SolvePerms(int ammount, int coins[]) throws Exception
    {
        ArrayList<solution> solutionList = new ArrayList<solution>();
        ArrayList<Integer> emptyList = new ArrayList<Integer>();
        solution CurrentSolution = new solution(emptyList);
        GetPerms(ammount, coins, CurrentSolution, solutionList);
        
        return solutionList;
    }
    
    
    private void GetPerms(int ammount, int coins[], solution CurrentSolution,   ArrayList<solution> mSolutions) throws Exception
    {
        int currentCoin = coins[0];
        
        if (currentCoin <= 0)
        {
            throw new Exception("Cant cope with negative or zero ammounts");
        }
        
        if (coins.length == 1)
        {
            if (ammount % currentCoin == 0)
            {
                CurrentSolution.add(ammount/currentCoin);
                mSolutions.add(CurrentSolution);
            }
            return;
        }
        
        // work out list with one less coin.
        int coinsDepth = coins.length;
        int reducedCoins[] = new int[(coinsDepth -1 )];
        for (int j = 0; j < coinsDepth - 1;j++)
        {
            reducedCoins[j] = coins[j+1];
        }
        
        
        // integer rounding okay;
        int numberOfPerms = ammount / currentCoin;
        
        for (int j = 0; j <= numberOfPerms; j++)
        {
            solution newSolution =  CurrentSolution.clone();
            newSolution.add(j);
            GetPerms(ammount - j * currentCoin,reducedCoins, newSolution, mSolutions ); 
        }
    }
    
    
    private class solution 
    {
        ArrayList<Integer> mNumberOfCoins;

        solution(ArrayList<Integer> anumberOfCoins)
        {
            mNumberOfCoins = anumberOfCoins;
        }
        
        @Override
        public String toString() {
            if (mNumberOfCoins != null && mNumberOfCoins.size() > 0)
            {
                String retval = mNumberOfCoins.get(0).toString();
                for (int i = 1; i< mNumberOfCoins.size();i++)
                {
                    retval += ","+mNumberOfCoins.get(i).toString();
                }
                return retval;
            }
            else
            {
                return "";
            }
        }
        
        @Override
        protected solution clone() 
        {
            return new solution((ArrayList<Integer>) mNumberOfCoins.clone());
        }

        public void add(int i) {
            mNumberOfCoins.add(i);
        }
    }

}

public static void main(String[] args) {

    int b,c,total = 15;
    int combos =1;
        for(int d=0;d<total/7;d++)
           {
             b = total - d * 7;
            for (int n = 0; n <= b /6; n++)
        {
                    combos++;

        }

        }

      System.out.print("TOTAL COMBINATIONS  = "+combos);
}

Below is a recursive backtracking solution I created, It lists and counts all possible combination of denominations (coins) that would add up to a given amount.

Both denominations and the amounts can be dynamic

public class CoinComboGenerate {  
      public static final int[] DENO = {1,6,7};
      public static final int AMOUNT = 15;
      public static int count = 0;
    
      public static void change(int amount) {
        change(amount, new ArrayList<>(),0);  
      }
    
      private static void change(int rem, List<Integer> coins, int pos) {    
        if (rem == 0) {
          count++;
          System.out.println(count+")"+coins);
          return;
        }
        
        while(pos<DENO.length){            
          if (rem >= DENO[pos]) {
            coins.add(DENO[pos]);
            change(rem - DENO[pos], coins,pos);
            coins.remove(coins.size() - 1);  //backtrack
          }
          pos++;
        }  
      }
    
      public static void main(String[] args) {
            change(AMOUNT);
      }   
    }

Output:
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]

The same problem for coins(1,5,10,25,50) has one of below solutions. The solution should satisfy below equation: 1*a + 5*b + 10*c + 25*d + 50*e == cents

public static void countWaysToProduceGivenAmountOfMoney(int cents) {
        
        for(int a = 0;a<=cents;a++){
            for(int b = 0;b<=cents/5;b++){
                for(int c = 0;c<=cents/10;c++){
                    for(int d = 0;d<=cents/25;d++){
                        for(int e = 0;e<=cents/50;e++){
                            if(1*a + 5*b + 10*c + 25*d + 50*e == cents){
                                System.out.println("1 cents :"+a+", 5 cents:"+b+", 10 cents:"+c);
                            }
                        }
                    }
                }
            }
        }
    }

This can be modified for any general solutions.