Apparently simple code

2007/02/01

Tags: C#

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);
}
}
comments powered by Disqus Updated: 2019-01-23 11:41:32 +0100 +0100, Version: 6668e21