Problem 31 - Coin Sum

Problem:

Please find the problem here.

Solution:

It is easier to think when the number is smaller.

The number of ways to represent 15 using any number of coin is:

number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 10 coin]
+
number of ways to represent 5 using coins (1, 2, 5) [by choosing using 1 10 coin]

Similarly, the number of ways to represent 15 using coin (1, 2, 5) is:

number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 5 coin]
+
number of ways to represent 10 using coins (1, 2) [by choosing using 1 5 coin]
+
number of ways to represent 5 using coins (1, 2) [by choosing using 2 5 coin]
+
number of ways to represent 0 using coins (1, 2) [by choosing using 3 5 coin]

Of course the last term is 1, and now you get the idea how to use recursion to find the number of ways. The code do exactly that.

Code:

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem031()
        {
            // Count the number of using different coins
            int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };
            Console.WriteLine(Way(200, coinValues, coinValues.Length - 1));
        }

        private static int Way(int value, int[] coinValues, int maxIndex)
        {
            // This is special because we know it is 1, the value is can always be represented as sum of 1 in only 1 way.
            if (maxIndex == 0)
            {
                return 1;
            }
            int maxValue = coinValues[maxIndex];
            return Enumerable.Range(0, value / maxValue + 1).Select(t => Way(value - maxValue * t, coinValues, maxIndex - 1)).Aggregate((x, y) => x + y);
        }
    }
}