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??

Guenna

here is a good solution with example: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ – Courser

Answer 1

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.

Natie

See my answer for a more practical take on this approach, with suggestions for the unspecified algorithms. – Godfree

Found this old thread. There are some adjustments when the denominations are relative, in which case the partial fraction decomposition gives terms like Ak/(x-ak)^bk and the coefficients of x^n gets more complicated. – Alberta

Answer 2

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.

Sciomancy

Shouldn't it be amount-coins[checkFromIndex]? – Theft

Answer 3

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

Indene

I think the method works the way it is supposed to. It tells you the distinct number of possibilities on how to make sum with coins vals[]. For example: 51 from [1,25] <-- 3 possible ways 1x51, 1x26+1x25, 2x25+1x1 10 from [2,3,5,6] <-- 5 ways: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. – Indene

This is a very elegant solution. Can you add little bit description what is the intuition here? I understand that you broke the problem into several subproblems : one per every denomination while sum remains constant (I was thinking of using sum to breakup the problem ex: find combinations for 1 then 2 then 3 and so on while reusing previous sums) – Desdemona

so how we would extend this to computer permutations instead of combinations ? – Jubilee

Answer 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

Nausea

questioner needs answer written in Java – Cristycriswell

Answer 5

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

Godfree

Thank you for an interesting approach using modular arithmetic. While reading about it, I learnt about primitive roots and their use on such equations. A question that I have is on gathering the powers of the primitive root g, that is g^(p-1)*i/d, call it g_d^i for all i < d. I can see why some of these may be repeated, for which you'll get factors of the form 1/(g_d^i - x)^r. Are you accounting for these as well? I'm trying to figure out how these multiplicities affect the coefficients A(j). – Alberta

@Diego It makes a mess, of course. Easiest to pick another prime, since in probability, this shouldn't be an issue. – Godfree

I would think this happens for any prime you pick. Right before solving the partial fractions. – Alberta

@Diego You're right. I shouldn't try to do math early in the morning. – Godfree

And I saw it's been a while since you posted this... I believe I figured it out in paper and am testing for the computer. When accounting for repeated roots, you get terms for each power below the total, say 1/(x - g_k)^r_k and then solve the partial fractions of the form A(k,r)/(x-g_k)^r where r <= r_k. The coefficients with the r_k are "easier" as you can substitute x = g_k after multiplying the denominators and everything just cancels out. The other terms give the linear system of equations (modulo p) by substituting other different values x= x_i. – Alberta

@Diego Go ahead and post an answer. Comments are not safe from rampaging moderators. – Godfree

Answer 6

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.

Livvi

Exactly as I said. In the knapsack solution, each state keeps the minimum number of coins used to get there. For this problem, you do something like dp[current_total] += dp[current_total - current_denomination]. – Livvi

Answer 7

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

Speos

Answer 8

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.

Getty

Answer 9

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

}

Disembody

Answer 10

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;

    }
}

Jeffries

Answer 11

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)

Seow

Answer 12

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

}

Beare

Answer 13

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

Renita

Answer 14

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

Arsenate

Answer 15

Dynamic Programming Solution

Given an array of denominations D = {d1, d2, d3, ... , dm} and a target amount W. Note that D doesn't need to be sorted.

Let T(i, j) be the number of combinations that make up amount j using only denominations on the left of the ith one (can include itself) in D.

We have:

• T(0, 0) = 1 : since the amount is 0, there is only 1 valid combination that makes up 0, which is the empty set.

• T(i, j) = T(i - 1, j) if D[i] > j

• T(i, j) = T(i - 1, j) + T(i, j - D[i]) if D[i] <= j

    public int change(int amount, int[] coins) {
        int m = coins.length;
        int n = amount;
  
        int[][] dp = new int[m + 1][n + 1];
  
        dp[0][0] = 1;
  
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (j < coins[i -  1]) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i -  1]];
                }
            }
        }
  
        return dp[m][n];
    }
  

Sonnnie

Answer 16

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

Storz

might want to offer some description – Gatt

Answer 17

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]

Francescafrancesco

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Ripp

Answer 18

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.

Benis