Apparently simple code …

Sometimes what looks simple is complex and what looks complex is simple. See if you can understand how this one calculates all the possible ways to give change for a certain amount of money given some kinds of coins. You MIT guys out there don’t count, you probably have read the solution 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);

Comments (5)

  1. barrkel says:

    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.

  2. lucabol says:

    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 …

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

  4. choatea says:

    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…

  5. lucabol says:

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