How to find all combinations of coins when given some dollar value [closed]

Question

I found a piece of code that I was writing for interview prep few months ago.

According to the comment I had, it was trying to solve this problem:

Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars), find all the combinations of coins that make up the dollar value. There are only pennies (1¢), nickels (5¢), dimes (10¢), and quarters (25¢) allowed.

For example, if 100 was given, the answer should be:

4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies  
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies  
etc.

I believe that this can be solved in both iterative and recursive ways. My recursive solution is quite buggy, and I was wondering how other people would solve this problem. The difficult part of this problem was making it as efficient as possible.

Statis

@akappa: penny = 1 cent; nickel = 5 cents; dime = 10 cents; quarter = 25 cents :) – Statis

@John T: code golf? I've never heard of that term! Anyway, I'm hoping to see some interesting answers, since SO community can solve any problem – Statis

I will also try to post my answer once I get home... still at work and I shouldn't be spending too much time on SO. – Statis

@blee code golf refers to solving a problem in the least amount of characters possible, with the programming language of your choice. Here are some that have been done on this website: stackoverflow.com/search?q=code+golf – Burglary

I seem to remember doing this problem a couple of times for Project Euler. – Bade

This is very similar to Project Euler Problem #31. Check out the answer forum (visible once you supply the correct answer) for other interesting solutions. – Sediment

should be community wiki – Listlessness

code-golf => stackoverflow.com/questions/tagged/code-golf – Farmergeneral

This problem is mentioned as an example exercise in SICP in Section 1.2.2 "Tree Recursion" – Hotchkiss

Answer 1

I looked into this once a long time ago, and you can read my little write-up on it. Here’s the Mathematica source.

By using generating functions, you can get a closed-form constant-time solution to the problem. Graham, Knuth, and Patashnik’s Concrete Mathematics is the book for this, and contains a fairly extensive discussion of the problem. Essentially you define a polynomial where the nth coefficient is the number of ways of making change for n dollars.

Pages 4-5 of the writeup show how you can use Mathematica (or any other convenient computer algebra system) to compute the answer for 10^10^6 dollars in a couple seconds in three lines of code.

(And this was long enough ago that that’s a couple of seconds on a 75Mhz Pentium...)

Preciado

Good answer, but minor quibbles: note that (1) This gives the number of ways, while for some reason the question asks for the actual set of all ways. Of course, there can be no way of finding the set in polynomial time, since the output itself has superpolynomially many entries (2) It is debatable whether a generating function is a "closed form" (see Herbert Wilf's wonderful book Generatingfunctionology: math.upenn.edu/~wilf/DownldGF.html) and if you mean an expression like (1+√5)^n, it takes Ω(log n) time to compute, not constant time. – Tumulus

Gentle introduction to dynamic programming. Also, I encourage anyone with a sequence problem to read generatingfunctionology. – Pinwheel

Thanks so much Andrew ... this explanation helped me out so much ...Posting the scala function below .. should some one need it – Emigrant

I believe the question at the start needs a slight correction because it asks "...using 1-, 10-, 25-, 50-, and 100-cent coins?" But then the write up defines the set a as the domain of f but a = {1,5,10,25,50,100}. There should be a 5- in the cent coins list. Otherwise the write up was fantastic, thanks! – Former

@Former Wow, you are right, thanks for noticing that! I will update it … – Preciado

Answer 2

Note: This only shows the number of ways.

Scala function:

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

Flapdoodle

Is there really one way to change 0? I guess there is no way to do that. – Whitford

It stems from the number of polynomial solutions n1 * coins(0) + n2 * coins(1) + ... + nN * coins(N-1) = money. So for money=0 and coins=List(1,2,5,10) the count for combinations (n1, n2, n3, n4) is 1 and the solution is (0, 0, 0, 0). – Heat

I cannot wrap my head around why this implementation works. Can someone explain me the algorithm behind ? – Raper

This is definitely the exact answer to problem 3 of exercise 1 of the coursera scala course. – Mediocrity

I believe that, if money == 0 but coins.isEmpty, it should not count as a sol'n. Therefore, the algo may be better served if the coins.isEmpty || money < 0 condition is ck'd for first. – Mitch

@AdrienLemaire here's my attempt at an explanation, if you're still interested. :) – Topliffe

Answer 3

I would favor a recursive solution. You have some list of denominations, if the smallest one can evenly divide any remaining currency amount, this should work fine.

Basically, you move from largest to smallest denominations.
Recursively,

1. You have a current total to fill, and a largest denomination (with more than 1 left). If there is only 1 denomination left, there is only one way to fill the total. You can use 0 to k copies of your current denomination such that k * cur denomination <= total.
2. For 0 to k, call the function with the modified total and new largest denomination.
3. Add up the results from 0 to k. That's how many ways you can fill your total from the current denomination on down. Return this number.

Here's my python version of your stated problem, for 200 cents. I get 1463 ways. This version prints all the combinations and the final count total.

#!/usr/bin/python

# find the number of ways to reach a total with the given number of combinations

cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}

def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
           if left % denominations[i]:
               return 0
           comb.append( (left/denominations[i], demoninations[i]) )
           i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

count_combs(cents, 0, [], None)

Stringfellow

Haven't ran it, but by going through your logic, it makes sense :) – Statis

You can replace the last two lines of the function with "return sum(count_combs(...) for ...)" - that way the list doesn't get materialized at all. :) – Religiose

Thanks for the tip. I'm always interested in ways to tighten up code. – Stringfellow

As discussed in another question, this code will give incorrect output if the list of denominations doesn't have 1 as the last value. You can add a small amount of code to the innermost if block to fix it (as I describe in my answer to the other question). – Korn

Answer 4

Scala function :

def countChange(money: Int, coins: List[Int]): Int = {

def loop(money: Int, lcoins: List[Int], count: Int): Int = {
  // if there are no more coins or if we run out of money ... return 0 
  if ( lcoins.isEmpty || money < 0) 0
  else{
    if (money == 0 ) count + 1   
/* if the recursive subtraction leads to 0 money left - a prefect division hence return count +1 */
    else
/* keep iterating ... sum over money and the rest of the coins and money - the first item and the full set of coins left*/
      loop(money, lcoins.tail,count) + loop(money - lcoins.head,lcoins, count)
  }
}

val x = loop(money, coins, 0)
Console println x
x
}

Emigrant

Thanks! This is a great start. But, I think this fails when "money" starts out being 0 :) . – Agnola

Answer 5

Here's some absolutely straightforward C++ code to solve the problem which did ask for all the combinations to be shown.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        printf("usage: change amount-in-cents\n");
        return 1;
    }

    int total = atoi(argv[1]);

    printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);

    int combos = 0;

    for (int q = 0; q <= total / 25; q++)
    {
        int total_less_q = total - q * 25;
        for (int d = 0; d <= total_less_q / 10; d++)
        {
            int total_less_q_d = total_less_q - d * 10;
            for (int n = 0; n <= total_less_q_d / 5; n++)
            {
                int p = total_less_q_d - n * 5;
                printf("%d\t%d\t%d\t%d\n", q, d, n, p);
                combos++;
            }
        }
    }

    printf("%d combinations\n", combos);

    return 0;
}

But I'm quite intrigued about the sub problem of just calculating the number of combinations. I suspect there's a closed-form equation for it.

Georgie

Surely this is C, not C++. – Botch

@George Phillips can u explain? – Holcombe

I think it's pretty straightforward. Basically, the idea is to iterate all quarters (using 0,1,2 .. max), and then iterate through all dimes based on the quarters used, etc.. – Midge

The downside for this solution is: if there are 50-cent, 100-cent, 500-cent coins, then we have to use 6-level loops... – Midge

This is pretty bad, if you have a dynamic denominations or you'll want to add another denomination then this won't work. – Sprouse

Answer 6

The code is using Java to solve this problem and it also works... This method may not be a good idea because of too many loops, but it's really a straight forward way.

public class RepresentCents {

    public static int sum(int n) {

        int count = 0;
        for (int i = 0; i <= n / 25; i++) {
            for (int j = 0; j <= n / 10; j++) {
                for (int k = 0; k <= n / 5; k++) {
                    for (int l = 0; l <= n; l++) {
                        int v = i * 25 + j * 10 + k * 5 + l;
                        if (v == n) {
                            count++;
                        } else if (v > n) {
                            break;
                        }
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(sum(100));
    }
}

Giese

Answer 7

The sub problem is a typical Dynamic Programming problem.

/* Q: Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars),
      find the number of combinations of coins that make up the dollar value.
      There are only penny, nickel, dime, and quarter.
      (quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent) */
/* A:
Reference: http://andrew.neitsch.ca/publications/m496pres1.nb.pdf
f(n, k): number of ways of making change for n cents, using only the first
         k+1 types of coins.

          +- 0,                        n < 0 || k < 0
f(n, k) = |- 1,                        n == 0
          +- f(n, k-1) + f(n-C[k], k), else
 */

#include <iostream>
#include <vector>
using namespace std;

int C[] = {1, 5, 10, 25};

// Recursive: very slow, O(2^n)
int f(int n, int k)
{
    if (n < 0 || k < 0)
        return 0;

    if (n == 0)
        return 1;

    return f(n, k-1) + f(n-C[k], k); 
}

// Non-recursive: fast, but still O(nk)
int f_NonRec(int n, int k)
{
    vector<vector<int> > table(n+1, vector<int>(k+1, 1));

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            if (i < 0 || j < 0) // Impossible, for illustration purpose
            {
                table[i][j] = 0;
            }
            else if (i == 0 || j == 0) // Very Important
            {
                table[i][j] = 1;
            }
            else
            {
                // The recursion. Be careful with the vector boundary
                table[i][j] = table[i][j-1] + 
                    (i < C[j] ? 0 : table[i-C[j]][j]);
            }
        }
    }

    return table[n][k];
}

int main()
{
    cout << f(100, 3) << ", " << f_NonRec(100, 3) << endl;
    cout << f(200, 3) << ", " << f_NonRec(200, 3) << endl;
    cout << f(1000, 3) << ", " << f_NonRec(1000, 3) << endl;

    return 0;
}

Midge

Your dynamic solutions requires k to be the length of C minus 1. a bit confusing. You can change it easily to support the real length of C. – Disgorge

Answer 8

This is a really old question, but I came up with a recursive solution in java that seemed smaller than all the others, so here goes -

 public static void printAll(int ind, int[] denom,int N,int[] vals){
    if(N==0){
        System.out.println(Arrays.toString(vals));
        return;
    }
    if(ind == (denom.length))return;             
    int currdenom = denom[ind];
    for(int i=0;i<=(N/currdenom);i++){
        vals[ind] = i;
        printAll(ind+1,denom,N-i*currdenom,vals);
    }
 }

Improvements:

  public static void printAllCents(int ind, int[] denom,int N,int[] vals){
        if(N==0){
            if(ind < denom.length) {
                for(int i=ind;i<denom.length;i++)
                    vals[i] = 0;
            }
            System.out.println(Arrays.toString(vals));
            return;
        }
        if(ind == (denom.length)) {
            vals[ind-1] = 0;
            return;             
        }

        int currdenom = denom[ind];
        for(int i=0;i<=(N/currdenom);i++){ 
                vals[ind] = i;
                printAllCents(ind+1,denom,N-i*currdenom,vals);
        }
     }

Rosco

Answer 9

Let C(i,J) the set of combinations of making i cents using the values in the set J.

You can define C as that:

(first(J) takes in a deterministic way an element of a set)

It turns out a pretty recursive function... and reasonably efficient if you use memoization ;)

Cade

Yeah, this ("dynamic programming", in a sense) is going to be the optimal solution. – Tumulus

you're right: take J as a list and not as a set: then first(J) brings to you the first element and J \ first(J) gives to you the rest of the list. – Cade

what form of math is this? – Dialogist

Answer 10

semi-hack to get around the unique combination problem - force descending order:

$denoms = [1,5,10,25]
def all_combs(sum,last) 
  return 1 if sum == 0
  return $denoms.select{|d| d &le sum && d &le last}.inject(0) {|total,denom|
           total+all_combs(sum-denom,denom)}
end

This will run slow since it won't be memoized, but you get the idea.

Phallicism

Answer 11

var countChange = function (money,coins) {
  function countChangeSub(money,coins,n) {
    if(money==0) return 1;
    if(money<0 || coins.length ==n) return 0;
    return countChangeSub(money-coins[n],coins,n) + countChangeSub(money,coins,n+1);
  }
  return countChangeSub(money,coins,0);
}

Rocker

Answer 12

This is my answer in Python. It does not use recursion:

def crossprod (list1, list2):
    output = 0
    for i in range(0,len(list1)):
        output += list1[i]*list2[i]

    return output

def breakit(target, coins):
    coinslimit = [(target / coins[i]) for i in range(0,len(coins))]
    count = 0
    temp = []
    for i in range(0,len(coins)):
        temp.append([j for j in range(0,coinslimit[i]+1)])


    r=[[]]
    for x in temp:
        t = []
        for y in x:
            for i in r:
                t.append(i+[y])
        r = t

    for targets in r:
        if crossprod(targets, coins) == target:
            print targets
            count +=1
    return count




if __name__ == "__main__":
    coins = [25,10,5,1]
    target = 78
    print breakit(target, coins)

Example output

    ...
    1 ( 10 cents)  2 ( 5 cents)  58 ( 1 cents)  
    4 ( 5 cents)  58 ( 1 cents)  
    1 ( 10 cents)  1 ( 5 cents)  63 ( 1 cents)  
    3 ( 5 cents)  63 ( 1 cents)  
    1 ( 10 cents)  68 ( 1 cents)  
    2 ( 5 cents)  68 ( 1 cents)  
    1 ( 5 cents)  73 ( 1 cents)  
    78 ( 1 cents)  
    Number of solutions =  121

Terrell

Answer 13

# short and sweet with O(n) table memory    

#include <iostream>
#include <vector>

int count( std::vector<int> s, int n )
{
  std::vector<int> table(n+1,0);

  table[0] = 1;
  for ( auto& k : s )
    for(int j=k; j<=n; ++j)
      table[j] += table[j-k];

  return table[n];
}

int main()
{
  std::cout <<  count({25, 10, 5, 1}, 100) << std::endl;
  return 0;
}

Frond

Answer 14

This is a simple recursive algorithm that takes a bill, then takes a smaller bill recursively until it reaches the sum, it then takes another bill of same denomination, and recurses again. See sample output below for illustration.

var bills = new int[] { 100, 50, 20, 10, 5, 1 };

void PrintAllWaysToMakeChange(int sumSoFar, int minBill, string changeSoFar)
{
    for (int i = minBill; i < bills.Length; i++)
    {
        var change = changeSoFar;
        var sum = sumSoFar;

        while (sum > 0)
        {
            if (!string.IsNullOrEmpty(change)) change += " + ";
            change += bills[i];

            sum -= bills[i]; 
            if (sum > 0)
            {
                PrintAllWaysToMakeChange(sum, i + 1, change);
            }
        }

        if (sum == 0)
        {
            Console.WriteLine(change);
        }
    }
}

PrintAllWaysToMakeChange(15, 0, "");

Prints the following:

10 + 5
10 + 1 + 1 + 1 + 1 + 1
5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
5 + 5 + 1 + 1 + 1 + 1 + 1
5 + 5 + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Irreclaimable

Answer 15

In Scala Programming language i would do it like this:

 def countChange(money: Int, coins: List[Int]): Int = {

       money match {
           case 0 => 1
           case x if x < 0 => 0
           case x if x >= 1 && coins.isEmpty => 0
           case _ => countChange(money, coins.tail) + countChange(money - coins.head, coins)

       }

  }

Lousy

Answer 16

I know this is a very old question. I was searching through the proper answer and couldn't find anything that is simple and satisfactory. Took me some time but was able to jot down something.

function denomination(coins, original_amount){
    var original_amount = original_amount;
    var original_best = [ ];

    for(var i=0;i<coins.length; i++){
      var amount = original_amount;
      var best = [ ];
      var tempBest = [ ]
      while(coins[i]<=amount){
        amount = amount - coins[i];
        best.push(coins[i]);
      }
      if(amount>0 && coins.length>1){
        tempBest = denomination(coins.slice(0,i).concat(coins.slice(i+1,coins.length)), amount);
        //best = best.concat(denomination(coins.splice(i,1), amount));
      }
      if(tempBest.length!=0 || (best.length!=0 && amount==0)){
        best = best.concat(tempBest);
        if(original_best.length==0 ){
          original_best = best
        }else if(original_best.length > best.length ){
          original_best = best;
        }  
      }
    }
    return original_best;  
  }
  denomination( [1,10,3,9] , 19 );

This is a javascript solution and uses recursion.

Laager

This solution only finds one denomination. The question was to find "all" denominations. – Reseau

Answer 17

Both: iterate through all denominations from high to low, take one of denomination, subtract from requried total, then recurse on remainder (constraining avilable denominations to be equal or lower to current iteration value.)

Sukiyaki

Answer 18

If the currency system allows it, a simple greedy algorithm that takes as many of each coin as possible, starting with the highest value currency.

Otherwise, dynamic programming is required to find an optimal solution quickly since this problem is essentially the knapsack problem.

For example, if a currency system has the coins: {13, 8, 1}, the greedy solution would make change for 24 as {13, 8, 1, 1, 1}, but the true optimal solution is {8, 8, 8}

Edit: I thought we were making change optimally, not listing all the ways to make change for a dollar. My recent interview asked how to make change so I jumped ahead before finishing to read the question.

Fantinlatour

the problem is not necessarily for one dollar -- it could 2 or 23, so your solution is still the only correct one. – Saloop

Answer 19

Below is a python program to find all combinations of money. This is a dynamic programming solution with order(n) time. Money is 1,5,10,25

We traverse from row money 1 to row money 25 (4 rows). Row money 1 contains the count if we only consider money 1 in calculating the number of combinations. Row money 5 produces each column by taking the count in row money r for the same final money plus the previous 5 count in its own row (current position minus 5). Row money 10 uses row money 5, which contains counts for both 1,5 and adds in the previous 10 count (current position minus 10). Row money 25 uses row money 10, which contains counts for row money 1,5,10 plus the previous 25 count.

For example, numbers[1][12] = numbers[0][12] + numbers[1][7] (7 = 12-5) which results in 3 = 1 + 2; numbers[3][12] = numbers[2][12] + numbers[3][9] (-13 = 12-25) which results in 4 = 0 + 4, since -13 is less than 0.

def cntMoney(num):
    mSz = len(money)
    numbers = [[0]*(1+num) for _ in range(mSz)]
    for mI in range(mSz): numbers[mI][0] = 1
    for mI,m in enumerate(money):
        for i in range(1,num+1):
            numbers[mI][i] = numbers[mI][i-m] if i >= m else 0
            if mI != 0: numbers[mI][i] += numbers[mI-1][i]
        print('m,numbers',m,numbers[mI])
    return numbers[mSz-1][num]

money = [1,5,10,25]
    num = 12
    print('money,combinations',num,cntMoney(num))

output:    
('m,numbers', 1, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
('m,numbers', 5, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3])
('m,numbers', 10, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('m,numbers', 25, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('money,combinations', 12, 4)

Pleo

Answer 20

Here's a C# function:

    public static void change(int money, List<int> coins, List<int> combination)
    {
        if(money < 0 || coins.Count == 0) return;
        if (money == 0)
        {
            Console.WriteLine((String.Join("; ", combination)));
            return;
        }

        List<int> copy = new List<int>(coins);
        copy.RemoveAt(0);
        change(money, copy, combination);

        combination = new List<int>(combination) { coins[0] };
        change(money - coins[0], coins, new List<int>(combination));
    }

Use it like this:

change(100, new List<int>() {5, 10, 25}, new List<int>());

It prints:

25; 25; 25; 25
10; 10; 10; 10; 10; 25; 25
10; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 10; 10; 25; 25; 25
5; 10; 10; 10; 10; 10; 10; 10; 25
5; 5; 10; 10; 10; 10; 25; 25
5; 5; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 10; 25; 25; 25
5; 5; 5; 10; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 10; 10; 10; 25; 25
5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 25; 25; 25
5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 10; 10; 25; 25
5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5

Sprouse

The output is pretty – First

Answer 21

/*
* make a list of all distinct sets of coins of from the set of coins to
* sum up to the given target amount.
* Here the input set of coins is assumed yo be {1, 2, 4}, this set MUST
* have the coins sorted in ascending order.
* Outline of the algorithm:
* 
* Keep track of what the current coin is, say ccn; current number of coins
* in the partial solution, say k; current sum, say sum, obtained by adding
* ccn; sum sofar, say accsum:
*  1) Use ccn as long as it can be added without exceeding the target
*     a) if current sum equals target, add cc to solution coin set, increase
*     coin coin in the solution by 1, and print it and return
*     b) if current sum exceeds target, ccn can't be in the solution, so
*        return
*     c) if neither of the above, add current coin to partial solution,
*        increase k by 1 (number of coins in partial solution), and recuse
*  2) When current denomination can no longer be used, start using the
*     next higher denomination coins, just like in (1)
*  3) When all denominations have been used, we are done
*/

#include <iostream>
#include <cstdlib>

using namespace std;

// int num_calls = 0;
// int num_ways = 0;

void print(const int coins[], int n);

void combine_coins(
                   const int denoms[], // coins sorted in ascending order
                   int n,              // number of denominations
                   int target,         // target sum
                   int accsum,         // accumulated sum
                   int coins[],        // solution set, MUST equal
                                       // target / lowest denom coin
                   int k               // number of coins in coins[]
                  )
{

    int  ccn;   // current coin
    int  sum;   // current sum

    // ++num_calls;

    for (int i = 0; i < n; ++i) {
        /*
         * skip coins of lesser denomination: This is to be efficient
         * and also avoid generating duplicate sequences. What we need
         * is combinations and without this check we will generate
         * permutations.
         */
        if (k > 0 && denoms[i] < coins[k - 1])
            continue;   // skip coins of lesser denomination

        ccn = denoms[i];

        if ((sum = accsum + ccn) > target)
            return;     // no point trying higher denominations now


        if (sum == target) {
            // found yet another solution
            coins[k] = ccn;
            print(coins, k + 1);
            // ++num_ways;
            return;
        }

        coins[k] = ccn;
        combine_coins(denoms, n, target, sum, coins, k + 1);
    }
}

void print(const int coins[], int n)
{
    int s = 0;
    for (int i = 0; i < n; ++i) {
        cout << coins[i] << " ";
        s += coins[i];
    }
    cout << "\t = \t" << s << "\n";

}

int main(int argc, const char *argv[])
{

    int denoms[] = {1, 2, 4};
    int dsize = sizeof(denoms) / sizeof(denoms[0]);
    int target;

    if (argv[1])
        target = atoi(argv[1]);
    else
        target = 8;

    int *coins = new int[target];


    combine_coins(denoms, dsize, target, 0, coins, 0);

    // cout << "num calls = " << num_calls << ", num ways = " << num_ways << "\n";

    return 0;
}

Paco

Answer 22

Lots of variations here but couldn't find a PHP solution for the number of combinations anywhere so I'll add one in.

/**
 * @param int $money The total value
 * @param array $coins The coin denominations
 * @param int $sum The countable sum
 * @return int
 */
function getTotalCombinations($money, $coins, &$sum = 0){
  if ($money == 0){
    return $sum++;
  } else if (empty($coins) || $money < 0){
    return $sum;
  } else {
      $firstCoin = array_pop(array_reverse($coins));
      getTotalCombinations($money - $firstCoin, $coins, $sum) + getTotalCombinations($money, array_diff($coins, [$firstCoin]), $sum);
  }
  return $sum;
}


$totalCombinations = getTotalCombinations($money, $coins);

Terrell

Answer 23

Straightforward java solution:

public static void main(String[] args) 
{    
    int[] denoms = {4,2,3,1};
    int[] vals = new int[denoms.length];
    int target = 6;
    printCombinations(0, denoms, target, vals);
}


public static void printCombinations(int index, int[] denom,int target, int[] vals)
{
  if(target==0)
  {
    System.out.println(Arrays.toString(vals));
    return;
  }
  if(index == denom.length) return;   
  int currDenom = denom[index];
  for(int i = 0; i*currDenom <= target;i++)
  {
    vals[index] = i;
    printCombinations(index+1, denom, target - i*currDenom, vals);
    vals[index] = 0;
  }
}

Arbutus

Answer 24

This is the improvement of Zihan's answer. The great deal of unnecessary loops comes when the denomination is just 1 cent.

It's intuitive and non-recursive.

    public static int Ways2PayNCents(int n)
    {
        int numberOfWays=0;
        int cent, nickel, dime, quarter;
        for (quarter = 0; quarter <= n/25; quarter++)
        {
            for (dime = 0; dime <= n/10; dime++)
            {
                for (nickel = 0; nickel <= n/5; nickel++)
                {
                    cent = n - (quarter * 25 + dime * 10 + nickel * 5);
                    if (cent >= 0)
                    {
                        numberOfWays += 1;
                        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, cent);
                    }                   
                }
            }
        }
        return numberOfWays;            
    }

Hinrichs

u cannot generalize this solution, so for example a new element comes up in that case you have to add another for loop – Lactoflavin

Answer 25

I found this neat piece of code in the book "Python For Data Analysis" by O'reily. It uses lazy implementation and int comparison and i presume it can be modified for other denominations using decimals. Let me know how it works for you!

def make_change(amount, coins=[1, 5, 10, 25], hand=None):
 hand = [] if hand is None else hand
 if amount == 0:
 yield hand
 for coin in coins:
 # ensures we don't give too much change, and combinations are unique
 if coin > amount or (len(hand) > 0 and hand[-1] < coin):
 continue
 for result in make_change(amount - coin, coins=coins,
 hand=hand + [coin]):
 yield result

Clan

Answer 26

public class Coins {

static int ac = 421;
static int bc = 311;
static int cc = 11;

static int target = 4000;

public static void main(String[] args) {


    method2();
}

  public static void method2(){
    //running time n^2

    int da = target/ac;
    int db = target/bc;     

    for(int i=0;i<=da;i++){         
        for(int j=0;j<=db;j++){             
            int rem = target-(i*ac+j*bc);               
            if(rem < 0){                    
                break;                  
            }else{                  
                if(rem%cc==0){                  
                    System.out.format("\n%d, %d, %d ---- %d + %d + %d = %d \n", i, j, rem/cc, i*ac, j*bc, (rem/cc)*cc, target);                     
                }                   
            }                   
        }           
    }       
}
 }

Fellah

Answer 27

Duh, I feel stupid right now. Below there is an overly complicated solution, which I'll preserve because it is a solution, after all. A simple solution would be this:

// Generate a pretty string
val coinNames = List(("quarter", "quarters"), 
                     ("dime", "dimes"), 
                     ("nickel", "nickels"), 
                     ("penny", "pennies"))
def coinsString = 
  Function.tupled((quarters: Int, dimes: Int, nickels:Int, pennies: Int) => (
    List(quarters, dimes, nickels, pennies) 
    zip coinNames // join with names
    map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
    map (t => t._1 + " " + t._2) // qty name
    mkString " "
  ))

def allCombinations(amount: Int) = 
 (for{quarters <- 0 to (amount / 25)
      dimes <- 0 to ((amount - 25*quarters) / 10)
      nickels <- 0 to ((amount - 25*quarters - 10*dimes) / 5)
  } yield (quarters, dimes, nickels, amount - 25*quarters - 10*dimes - 5*nickels)
 ) map coinsString mkString "\n"

Here is the other solution. This solution is based on the observation that each coin is a multiple of the others, so they can be represented in terms of them.

// Just to make things a bit more readable, as these routines will access
// arrays a lot
val coinValues = List(25, 10, 5, 1)
val coinNames = List(("quarter", "quarters"), 
                     ("dime", "dimes"), 
                     ("nickel", "nickels"), 
                     ("penny", "pennies"))
val List(quarter, dime, nickel, penny) = coinValues.indices.toList


// Find the combination that uses the least amount of coins
def leastCoins(amount: Int): Array[Int] =
  ((List(amount) /: coinValues) {(list, coinValue) =>
    val currentAmount = list.head
    val numberOfCoins = currentAmount / coinValue
    val remainingAmount = currentAmount % coinValue
    remainingAmount :: numberOfCoins :: list.tail
  }).tail.reverse.toArray

// Helper function. Adjust a certain amount of coins by
// adding or subtracting coins of each type; this could
// be made to receive a list of adjustments, but for so
// few types of coins, it's not worth it.
def adjust(base: Array[Int], 
           quarters: Int, 
           dimes: Int, 
           nickels: Int, 
           pennies: Int): Array[Int] =
  Array(base(quarter) + quarters, 
        base(dime) + dimes, 
        base(nickel) + nickels, 
        base(penny) + pennies)

// We decrease the amount of quarters by one this way
def decreaseQuarter(base: Array[Int]): Array[Int] =
  adjust(base, -1, +2, +1, 0)

// Dimes are decreased this way
def decreaseDime(base: Array[Int]): Array[Int] =
  adjust(base, 0, -1, +2, 0)

// And here is how we decrease Nickels
def decreaseNickel(base: Array[Int]): Array[Int] =
  adjust(base, 0, 0, -1, +5)

// This will help us find the proper decrease function
val decrease = Map(quarter -> decreaseQuarter _,
                   dime -> decreaseDime _,
                   nickel -> decreaseNickel _)

// Given a base amount of coins of each type, and the type of coin,
// we'll produce a list of coin amounts for each quantity of that particular
// coin type, up to the "base" amount
def coinSpan(base: Array[Int], whichCoin: Int) = 
  (List(base) /: (0 until base(whichCoin)).toList) { (list, _) =>
    decrease(whichCoin)(list.head) :: list
  }

// Generate a pretty string
def coinsString(base: Array[Int]) = (
  base 
  zip coinNames // join with names
  map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
  map (t => t._1 + " " + t._2)
  mkString " "
)

// So, get a base amount, compute a list for all quarters variations of that base,
// then, for each combination, compute all variations of dimes, and then repeat
// for all variations of nickels.
def allCombinations(amount: Int) = {
  val base = leastCoins(amount)
  val allQuarters = coinSpan(base, quarter)
  val allDimes = allQuarters flatMap (base => coinSpan(base, dime))
  val allNickels = allDimes flatMap (base => coinSpan(base, nickel))
  allNickels map coinsString mkString "\n"
}

So, for 37 coins, for example:

scala> println(allCombinations(37))
0 quarter 0 dimes 0 nickels 37 pennies
0 quarter 0 dimes 1 nickel 32 pennies
0 quarter 0 dimes 2 nickels 27 pennies
0 quarter 0 dimes 3 nickels 22 pennies
0 quarter 0 dimes 4 nickels 17 pennies
0 quarter 0 dimes 5 nickels 12 pennies
0 quarter 0 dimes 6 nickels 7 pennies
0 quarter 0 dimes 7 nickels 2 pennies
0 quarter 1 dime 0 nickels 27 pennies
0 quarter 1 dime 1 nickel 22 pennies
0 quarter 1 dime 2 nickels 17 pennies
0 quarter 1 dime 3 nickels 12 pennies
0 quarter 1 dime 4 nickels 7 pennies
0 quarter 1 dime 5 nickels 2 pennies
0 quarter 2 dimes 0 nickels 17 pennies
0 quarter 2 dimes 1 nickel 12 pennies
0 quarter 2 dimes 2 nickels 7 pennies
0 quarter 2 dimes 3 nickels 2 pennies
0 quarter 3 dimes 0 nickels 7 pennies
0 quarter 3 dimes 1 nickel 2 pennies
1 quarter 0 dimes 0 nickels 12 pennies
1 quarter 0 dimes 1 nickel 7 pennies
1 quarter 0 dimes 2 nickels 2 pennies
1 quarter 1 dime 0 nickels 2 pennies

Pick

Answer 28

This blog entry of mine solves this knapsack like problem for the figures from an XKCD comic. A simple change to the items dict and the exactcost value will yield all solutions for your problem too.

If the problem were to find the change that used the least cost, then a naive greedy algorithm that used as much of the highest value coin might well fail for some combinations of coins and target amount. For example if there are coins with values 1, 3, and 4; and the target amount is 6 then the greedy algorithm might suggest three coins of value 4, 1, and 1 when it is easy to see that you could use two coins each of value 3.

• Paddy.

Wynne

Answer 29

I implemented this puzzle in C#, I think it's kind of different from other answers. In addition I added comments to make my algorithm more understandable. It was a very nice puzzle.

Start from larger coin and look on all Q,D,N and fill up the remainder with pennies.

So I can start with having 0 quarter, 0 dime and 0 nickel and the rest with pennies

For each coin, I have ($Amount / $Change) + 1, which $Amount is the input parameter and $Change is [Q]uarter or [D]ime or [N]ickel. So, assuming the input parameter is $1,

• I have ($1 / 0.25) + 1 = 5 choices for Quarter (0, 1, 2, 3, 4) -- qLoop variable in my code
• For the same $1, I will have ($1 / 0.10) + 1 = 11 options for Dime (0, 1, 2 ,3, 4, 5, 6, 7, 8, 9, 10) -- dLoop variable in my code
• The same for Nickel, I will have ($1 / 0.05) + 1 = 21 option (0 through 20) -- nLoop variable in my code

Note that in each loop, I have to use the reminder from outer loop.

As an example, if I pick 1 quarter, (where q is 1), I have $1 - 0.25 left for the inner loop (Dime loop) and so on

static void CoinCombination(decimal A)
{
    decimal[] coins = new decimal[] { 0.25M, 0.10M, 0.05M, 0.01M };

    // Loop for Quarters
    int qLoop = (int)(A / coins[0]) + 1;
    for (int q = 0; q < qLoop; q++)
    {
        string qS = $"{q} quarter(s), ";
        decimal qAmount = A - (q * coins[0]);
        Console.Write(qS);

        // Loop for Dimes
        int dLoop = (int)(qAmount / coins[1]) + 1;
        for (int d = 0; d < dLoop; d++)
        {
            if (d > 0)
                Console.Write(qS);
            string dS = $"{d} dime(s), ";
            decimal dAmount = qAmount - (d * coins[1]);
            Console.Write(dS);

            // Loop for Nickels
            int nLoop = (int)(dAmount / coins[2]) + 1;
            for (int n = 0; n < nLoop; n++)
            {
                if (n > 0)
                    Console.Write($"{qS}{dS}");
                string nS = $"{n} nickel(s), ";
                decimal nAmount = dAmount - (n * coins[2]);
                Console.Write(nS);

                // Fill up with pennies the remainder
                int p = (int)(nAmount / coins[3]);
                string pS = $"{p} penny(s)";
                Console.Write(pS);

                Console.WriteLine();
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}

Output

Grissom

Answer 30

The following one-liner in Mathematica produces the desired result

parts[n_]:=Flatten[Table[{(n-i)/25,(i-j)/10,(j-k)/5,k},{i,n,0,-25},{j,i,0,-10},{k,j,0,-5}],2]

The table trivially builds up all combinations by iterating through all ways of how many coins of a bigger kind fit into n, while repeating the same steps with coins of smaller kind for the remainder. The implementation should be similarly trivial in any other programming language.

The output is a list of elements with the notation:

{number of quarters, number of dimes, number of nickels, number of cents}

The intuition behind the construction can be read off of an example:

parts[51]

Neutrality

Answer 31

PHP Code to breakdown an amount into denominations:

//Define the denominations    
private $denominations = array(1000, 500, 200, 100, 50, 40, 20, 10, 5, 1);
/**
 * S# countDenomination() function
 * 
 * @author Edwin Mugendi <[email protected]>
 * 
 * Count denomination
 * 
 * @param float $original_amount Original amount
 * 
 * @return array with denomination and count
 */
public function countDenomination($original_amount) {
    $amount = $original_amount;
    $denomination_count_array = array();
    foreach ($this->denominations as $single_denomination) {

        $count = floor($amount / $single_denomination);

        $denomination_count_array[$single_denomination] = $count;

        $amount = fmod($amount, $single_denomination);
    }//E# foreach statement

    var_dump($denomination_count_array);
    return $denomination_count_array;
    //return $denomination_count_array;
}

//E# countDenomination() function

Soliloquy

Answer 32

Below is python solution:

    x = []
    dic = {}
    def f(n,r):
        [a,b,c,d] = r
        if not dic.has_key((n,a,b,c,d)): dic[(n,a,b,c,d)] = 1
        if n>=25:
            if not dic.has_key((n-25,a+1,b,c,d)):f(n-25,[a+1,b,c,d])
            if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
            if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        elif n>=10:
            if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
            if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        elif n>=5:
            if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        elif n>=1:
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        else:
            if r not in x:
                x.extend([r])

    f(100, [0,0,0,0])
    print x

Tutelage

Answer 33

Here is a python based solution that uses recursion as well as memoization resulting in a complexity of O(mxn)

    def get_combinations_dynamic(self, amount, coins, memo):
    end_index = len(coins) - 1
    memo_key = str(amount)+'->'+str(coins)
    if memo_key in memo:
        return memo[memo_key]
    remaining_amount = amount
    if amount < 0:
        return []
    if amount == 0:
        return [[]]
    combinations = []
    if len(coins) <= 1:
        if amount % coins[0] == 0:
            combination = []
            for i in range(amount // coins[0]):
                combination.append(coins[0])
            list.sort(combination)
            if combination not in combinations:
                combinations.append(combination)
    else:
        k = 0
        while remaining_amount >= 0:
            sub_combinations = self.get_combinations_dynamic(remaining_amount, coins[:end_index], memo)
            for combination in sub_combinations:
                temp = combination[:]
                for i in range(k):
                    temp.append(coins[end_index])
                list.sort(temp)
                if temp not in combinations:
                    combinations.append(temp)
            k += 1
            remaining_amount -= coins[end_index]
    memo[memo_key] = combinations
    return combinations

Wineskin

Okay I doubt the above has polynomial run time. Not sure if we can have polynomial run time at all. But what I have observed is the above runs faster than the non-memoized version in many cases. I'll continue to research why – Wineskin

Answer 34

The below java solution which will print the different combinations as well. Easy to understand. Idea is

for sum 5

The solution is

    5 - 5(i) times 1 = 0
        if(sum = 0)
           print i times 1
    5 - 4(i) times 1 = 1
    5 - 3 times 1 = 2
        2 -  1(j) times 2 = 0
           if(sum = 0)
              print i times 1 and j times 2
    and so on......

If the remaining sum in each loop is lesser than the denomination ie if remaining sum 1 is lesser than 2, then just break the loop

The complete code below

Please correct me in case of any mistakes

public class CoinCombinbationSimple {
public static void main(String[] args) {
    int sum = 100000;
    printCombination(sum);
}

static void printCombination(int sum) {
    for (int i = sum; i >= 0; i--) {
        int sumCopy1 = sum - i * 1;
        if (sumCopy1 == 0) {
            System.out.println(i + " 1 coins");
        }
        for (int j = sumCopy1 / 2; j >= 0; j--) {
            int sumCopy2 = sumCopy1;
            if (sumCopy2 < 2) {
                break;
            }
            sumCopy2 = sumCopy1 - 2 * j;
            if (sumCopy2 == 0) {
                System.out.println(i + " 1 coins " + j + " 2 coins ");
            }
            for (int k = sumCopy2 / 5; k >= 0; k--) {
                int sumCopy3 = sumCopy2;
                if (sumCopy2 < 5) {
                    break;
                }
                sumCopy3 = sumCopy2 - 5 * k;
                if (sumCopy3 == 0) {
                    System.out.println(i + " 1 coins " + j + " 2 coins "
                            + k + " 5 coins");
                }
            }
        }
    }
}

}

Transitory

Answer 35

Java solution

import java.util.Arrays;
import java.util.Scanner;


public class nCents {



public static void main(String[] args) {

    Scanner input=new Scanner(System.in);
    int cents=input.nextInt();
    int num_ways [][] =new int [5][cents+1];

    //putting in zeroes to offset
    int getCents[]={0 , 0 , 5 , 10 , 25};
    Arrays.fill(num_ways[0], 0);
    Arrays.fill(num_ways[1], 1);

    int current_cent=0;
    for(int i=2;i<num_ways.length;i++){

        current_cent=getCents[i];

        for(int j=1;j<num_ways[0].length;j++){
            if(j-current_cent>=0){
                if(j-current_cent==0){
                    num_ways[i][j]=num_ways[i-1][j]+1;
                }else{
                    num_ways[i][j]=num_ways[i][j-current_cent]+num_ways[i-1][j];
                }
            }else{
                num_ways[i][j]=num_ways[i-1][j];
            }


        }


    }



    System.out.println(num_ways[num_ways.length-1][num_ways[0].length-1]);

}

}

Primary

Answer 36

I used a really simple loop to solve this in a BlackJack game I'm writing in HTML5 using the Isogenic Game Engine. You can see a video of the BlackJack game which shows the chips that were used to make up a bet from the bet value on the BlackJack table above the cards: http://bit.ly/yUF6iw

In this example, betValue equals the total value that you wish to divide into "coins" or "chips" or whatever.

You can set the chipValues array items to whatever your coins or chips are worth. Make sure that the items are ordered from lowest value to highest value (penny, nickel, dime, quarter).

Here is the JavaScript:

// Set the total that we want to divide into chips
var betValue = 191;

// Set the chip values
var chipValues = [
    1,
    5,
    10,
    25
];

// Work out how many of each chip is required to make up the bet value
var tempBet = betValue;
var tempChips = [];
for (var i = chipValues.length - 1; i >= 0; i--) {
    var chipValue = chipValues[i];
    var divided = Math.floor(tempBet / chipValue);

    if (divided >= 1) {
        tempChips[i] = divided;
        tempBet -= divided * chipValues[i];
    }

    if (tempBet == 0) { break; }
}

// Display the chips and how many of each make up the betValue
for (var i in tempChips) {
    console.log(tempChips[i] + ' of ' + chipValues[i]);
}

You obviously don't need to do the last loop and it is only there to console.log the final array values.

Garden

It seems you are finding only one combination for the bet. That's not what was asked in the question. – Zenobia

Answer 37

public static int calcCoins(int cents){
        return coins(cents,new int[cents+1]);
    }
    public static int coins(int cents,int[] memo){
        if(memo[cents] != 0){
            return -1;
        }
        int sum = 0;
        int arr[] = {25,10,5,1};

        for (int i = 0; i < arr.length; i++) {
            if(cents/arr[i] != 0){
                int temp = coins(cents-arr[i],memo);
                if(temp == 0){
                    sum+=1;
                } else if(temp == -1){
                    sum +=0;
                }
                else{
                    sum += temp;
                }
            } 
        }
        memo[cents] = sum;
        return sum;
    }

Dasteel

can you please explain what this code does and why it answers the question? Code only answers are discouraged. – Excavate