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);
Console.WriteLine(i);
}

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

Tags