Apparently simple code

Tags: csharp @ 2007/02/02

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