How to find all combinations of coins when given s

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, nickels, dimes, and quarters allowed. (quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent)

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.

This can be solved in both iterative and recursive ways, I believe. 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.

Answer 1

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)

       }

  }

Answer 2

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:
            comb.append( (left, denominations[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)

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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