Enumerating all the ways of making change


Today's Little Program enumerates all the ways of making change for a particular amount given a set of available denominations.

The algorithm is straightforward. To make change for a specific amount from a set of available denominations, you can take one denomination and decide how many of those you want to use. Then use the remaining denominations to make change for the remainder.

For example, if the available coins have values [1, 5, 10, 25] and you want to make change for 60 cents, you first decide how many 25-cent pieces you want to use. If you use none, then you need to make change for 60 cents using just [1, 5, 10]. If you use one, then you need to make change for 35 cents using just [1, 5, 10]. And if you use two, then you need to make change for 10 cents using just [1, 5, 10].

(We use the largest coin first to reduce the number of dead ends, like asking "Please make change for 83 cents using only 10-cent coins.")

function MakeChange(coins, total, f) {
 if (total == 0) { f([]); return; }
 if (coins.length == 0) return;

 var coin = coins[coins.length - 1];
 var remaining = coins.slice(0, -1);
 var used = [];
 for (var target = total; target >= 0; target -= coin) {
  MakeChange(remaining, target, function(s) {
   f(used.concat(s));
  });
  used.push(coin);
 }
}

MakeChange([1, 5, 10, 25], 60, console.log.bind(console));

First, we take care of some base cases. To make change for zero cents, we simply use zero coins. And it's not possible to make change for a nonzero amount with no coins.

Otherwise, we take the highest denomination coin and try using zero of them, then one of them, and so on, until we exceed the total amount necessary.

There are related problems, such as determining whether a particular amount of change can even be made, given a collection of denominations and calculating the number of ways change can be made rather than enumerating them. But I like enumeration problems.

Comments (29)
  1. Of all the ways to change X cents using coins of values {C_1, C_2, ...}, only a few (or one!) are "canonical": blogs.msdn.com/.../rules-for-making-change.aspx it would be interesting to pass an "is canonical" indicator to f.

  2. Brian_EE says:

    @Maurits: With an attitude like that (referring to the rules in the linked blog post) the US will never eliminate pennies ( http://www.youtube.com/watch?v=y5UT04p5f7U ) nor displace the $1 bill with the $1 coin ( http://www.dollarcoinalliance.org/facts-about-the-dollar-coin ) - both things that currency-issuing authorities in other regions of this world have accomplished.

    Also, I would be interested to know if there is a way to incoporporate non-monetary items such as HOPE into the change algorithm.... No? I never thought so either. </politics>

  3. Ken in NH says:

    @Brian_EE: Yes, because of attitude. They keep trying to make [maybe entice is a better verb here] people use dollar coins, but it does not take hold because US citizens like what they like. In private enterprise, the company that attempts to market an unpopular product will cut losses and look for a better alternative (such as reinvesting in their more popular, proven products). In government, if something fails (such as Amtrak), well we must give it more funding!

  4. Ken in NH says:

    I think a slight tweak would make this work more like real world conditions. If the coins array is an array of objects like this: "{ coin: 25, count: 5 }" then the for loop can decrement the per coin count and test for 0 so the coin drawer need not contain an infinite amount of each coin type.

  5. Ross Presser says:

    I've long been interested in a related problem: if I have sufficient coins and so does the teller, how much should I overpay to minimize the number of coins exchanged? or the number of coins I get back?

    For example, if I owe $0.48, I could pay with a quarter, two dimes and three pennies, receiving nothing back (6 coins exchanged). Or I could pay with two quarters and get two pennies back (four coins exchanged).

  6. Brian_EE says:

    @Ross Presser: My goal is usually "What transaction minimizes the weight in my pocket." So, now we should also factor in the weight of each coin and optimize around weight exchanged (maximum given by consumer, minimum returned by teller).

  7. alegr1 says:

    >My goal is usually "What transaction minimizes the weight in my pocket."

    And this is also why dollar coins are not taking off.

  8. morlamweb says:

    @Ross Presser, Brian EE, others: my goal when using coin currency is "how many of those damn pennies can I use?" I typically have a small number of pennies floating around in my wallet that are damn near useless for most of my cash transactions.  On the rare occasion where pennies can help me make exact change, then I'll try to unload as many of them as possible, even if that means exchanging more coins than necessary. Otherwise, when I get home, I dump the pennies into a jar and, when it's full, take it somewhere that I can turn it into a more useful form of currency.

    [I use a different approach. I bring all my pennies when I use self-checkout, because the machine doesn't get mad when I feed it 30 pennies. -Raymond]
  9. ErikF says:

    Another refinement of this algorithm would be to determine at the beginning what the smallest denomination of coinage is and round to that, for countries where there are no denominations of 1 anymore:

    function RoundValue(coins, total) {

     coins = coins || [];

     var roundTo = null;

     coins.forEach(function(x) { if ((roundTo === null) || (x < roundTo)) roundTo = x; });

     if ((roundTo > 0) && (total > 0)) {

       var roundAmt = total % roundTo;

       if (roundAmt < Math.round(roundTo / 2))

         return total - roundAmt;

       else

         return total + (roundTo - roundAmt);

     } else { return 0; }

    }

    function MakeChange(coins, total, f) {

     total = RoundValue(coins, total);

     [...]

    }

    (Naturally, this would only be required for coins as debit and credit card transactions do not normally round!)

  10. Rick C says:

    ErikF, while that's an interesting variation, why would you pass the function a type of coin that doesn't exist?

  11. Brian_EE says:

    @alegr1: I would gladly give up dollar bills for dollar coins. I'm in the "pro" camp on that. I don't see that ti conflicts with minimizing weight of the coins I do carry when processing a transaction.

    @Raymond: "I bring all my pennies when I use self-checkout" - I refuse to use self-checkout lines. Why should I do the work of scanning and bagging my own purchases (i.e. the "cashier's job") when the establishment isn't discounting my bill for the labor cost savings that they are benefiting from. This has the side benefit of helping to keep cashiers employed.

    [Well, I'm okay with using self-checkout if it lets me unload all my pennies. -Raymond]
  12. voo says:

    When I was a student I had a big bowl of pennies (inherited from friends actually) which we used for playing poker. A friend of mine once counted them - it contained less than a year's worth of pennies - and came to $7.88 if I remember correctly..

    Annoying things, still hoping more EU countries get rid of 1 and 2 cent - heck I'm fine if we get rid of 5 cent too if we're at it, they don't really serve any useful purpose apart from obscuring the real price of items..

  13. > This has the side benefit of helping to keep cashiers employed

    en.wikipedia.org/.../Parable_of_the_broken_window

  14. Checkout operator says:

    @Brian_EE We really can't stand people like you. First time I've ever felt the need to comment on Raymond's blog, this attitude makes our jobs a lot more difficult.

    > This has the side benefit of helping to keep cashiers employed.

    This is the excuse a lot of you seem to use, but I've never heard anyone back it up as anything other than self-justification.

  15. Joshua says:

    @Checkout operator: The bank cashiers don't like it much either.

  16. morlamweb says:

    I'd say that no one likes to count pennies (or the smallest denomination of any currency, really).  Not even me.  I used to roll pennies and bring them to the bank regularly, but the face value of a roll of pennies just wasn't worth the time investment to count out 50 coins (and weed out the occasional Canadian penny); thus, the jar o' pennies.  I've found it much easier to dump the coins into the nearest coin-counting machine when the jar is full.

  17. Boris says:

    I haven't used self-checkout much, but I suppose another advantage is that non-technical people are going to avoid it, thus leaving it open for those who have taken the time to learn it. Also, you won't have the situation where three or four machines are standing there useless, unoccupied, just because the store has no cashiers to spare at the moment.

  18. > I bring all my pennies when I use self-checkout, because the machine doesn't get mad when I feed it 30 pennies

    Interesting...

    As a former cashier, I can testify that *cashiers* don't get mad when you feed them 30 pennies. The *people behind you* might get mad if you pull out your change, or your checkbook, or ask for cigarettes.

    In all the grocery stores I've been to, I've noticed that every human cashier has their own dedicated queue, but there is a shared queue for the self-checkout machines. And I've seen shared human-cashier queues in plenty of non-grocery stores: Fry's, Kohl's, Ross. But I've never seen a place with a shared self queue and a shared human-cashier queue.

  19. Checkout operator says:

    > As a former cashier, I can testify that *cashiers* don't get mad when you feed them 30 pennies.

    @Maurits Say what? Every checkout operator I've ever known has hated trying to count 30 pennies, and desperately wanted to say something along the lines of "We're not a damn bank!"

  20. Joker_vD says:

    How to make pennies go:

    1. Make everyone to round all cash payments down to the closest 5 cents. $1.21 becomes $1.20, $2.49 becomes $2.45, $3.65 stays $3.65. You can't round up because then you just charge the payer additional money for nothing.

    2. Smelt the damn coins and make a statute of my image from them.

    3. ?????

    4. PROFIT!

  21. Falcon says:

    @Joker_vD:

    Actually, in Australia, we DO round to the nearest 5 cents for cash transactions, so a $2.49 purchase would cost you $2.50.

  22. cheong00 says:

    [I use a different approach. I bring all my pennies when I use self-checkout, because the machine doesn't get mad when I feed it 30 pennies. -Raymond]

    That reminds me of an instance when a friend of mine worked for university's library, someone pay $500 bill for overdue penalty of $2 on Saturday near closing hour, after he packed all the bank notes above $100 in face-value to safe already.

    In the end that "someone" received a few hundred coins as change for what he had done.

  23. Neil says:

    How much commission do those coin-counting machines rake in?

  24. prunoki says:

    I have a jar I keep for cents and when it is full, I give it to the first lucky beggar.

  25. Brian_EE says:

    @Neil: Coinstar charges 9% unless you get the money as a gift card for one of their partners.

    @Checkout Operator: I put myself through college partly on a 5-year "career" in retail. I'm pretty sure that I can "stand myself". And if checking out customers is so annoying to you, I might suggest you try a different career. It is only common sense that automation reduces jobs in those industries that employ it (auto is a good case study, there are plenty of papers on the issue). I am also pretty sure that if all people and businesses quit sending items by mail, then the USPS would go out of business - including those employed.

  26. Scarlet Manuka says:

    @Maurits: I regularly shop at places which have both a shared self-checkout queue and a shared human-cashier queue.

  27. Drak says:

    @Rick C: how do you mean, pass in coins that do not exist?

    Here in the Netherlands, we have prices like 9.99, but we do not use the 1 and 2 cent coins. So 9.99 becomes 10 for those people paying in cash and stays 9.99 for those paying with their card.

    If you keep a good tally on your total you can walk away with 2 cents 'profit' each time you shop (9.92 would become 9.90).

  28. GregM says:

    "@Maurits: I regularly shop at places which have both a shared self-checkout queue and a shared human-cashier queue."

    and I regularly shop at places that have no shared queues.

  29. French guy says:

    Having a 2-cent coin and a 50-cent coin would lighten your pockets, since it would greatly reduce the number of pennies and quarters needed.

Comments are closed.

Skip to main content