Apparently simple code - Luca Bolognese

Apparently simple code

Luca -

☕ 1 min. read

Sometimes what looks sim­ple is com­plex and what looks com­plex is sim­ple. See if you can un­der­stand how this one cal­cu­lates all the pos­si­ble ways to give change for a cer­tain amount of money given some kinds of coins. You MIT guys out there don’t count, you prob­a­bly have read the so­lu­tion in the same book I have.

BTW: the code works with the LINQ May CTP

using System;

using System.Collections.Generic;

using System.Text;

using System.Query;

using System.Xml.XLinq;
class Program
static void Main(string[] args)
var coins = new int[] { 1, 5, 10, 25, 50 };

var i = ChangeComb(100, coins);

static int ChangeComb(int amount, IEnumerable<int> coins)
if (amount == 0) return 1;
if (amount < 0) return 0;
if (coins.Count() == 0) return 0;

return ChangeComb(amount, coins.Skip(1)) +
ChangeComb(amount - coins.First(), coins);


I don't get it - the code is straightforward recursion, there's nothing complex about it at all. If you've competed in any programming competitions, these kinds of problems are entry-level stuff.
The number of ways is 1 if there's no sum left, otherwise it's the number of ways by using all the remaining coins (i.e. skipping this denomination) plus the number of ways by using the coin (i.e. subtracting its value from the amount). It's immediately obvious.

Well ... to me it is not 'immediately obvious'. I had to sketch it on my whiteboard to visualize it. I guess I'm a much worse programmer than you are.
Anyhow, I would have never thought of this algo if someone gave me the text of the problem. I would have come up with something way more convoluted.
But again, that's just me ...

Charlie Calvert's Community Bl


Welcome to the twenty-first Community Convergence. I'm Charlie Calvert, the C# Community PM, and this

This doesn't work. (At least past 9)  It counts giving (one 5 and five 1's) and (five 1's and one 5) and similar reversals as being distinct.  It's still pretty cool though.  I implemented this to run on .NET 1.1 to check it out.  When it gave these results, I thought it was strange, so I downloaded and ran it on the LINQ May CTP that you originally tested it on, and they give the same result.  I guess if you consider the order in which you give the types of coins, it works.  Small gripe I know...

When I try to get 10 with [1,5] or [5,1] it gives me 3 as a result:(111111111)(111115)(55). It is not double counting the reversal. When I try to get 15 with [1,5] it gives me 4, which is correct again. Am I misunderstanding you?
BTW: if you try [1,5,5] you get 10. It considers the two 5s as different coins. If you don't want this behavior you can simply rename ChangeComb as ChangeCompTemp and add:
static int ChangeComb(int amount, IEnumerable<int> coins)
     return ChangeCompTemp(amount, coins.Distinct());

0 Webmentions

These are webmentions via the IndieWeb and