Solution: The Coin Change Problem

using System;
class Program
{
    /// <summary>
    /// Finds the number of ways that the given number of cents can be represented.
    /// </summary>
    /// <param name="denoms">Values of the coins available.</param>
    /// <param name="denomsLength">Number of denoms.</param>
    /// <param name="amount">Given cent amount.</param>
    /// <returns>The number of ways that the given number of cents can be represented.</returns>
    public static int CountChange(int[] denoms, int denomsLength, int amount)
    {
        // If amount is 0 there is 1 solution
        // (do not include any coin)
        if (amount == 0)
        {
            return 1;
        }
        // If n is less than 0 then no
        // solution exists
        if (amount < 0 || denomsLength <= 0)
        {
            return 0;
        }
        // If there are no coins and n
        // is greater than 0, then no
        // solution exist
        if (denomsLength <= 0 && amount >= 1)
        {
            return 0;
        }
        // Count is sum of solutions
        // (i) including denoms[len(denoms) - 1]
        // (ii) excluding denoms[len(denoms) - 1]
        return CountChange(denoms, denomsLength - 1, amount) + CountChange(denoms, denomsLength, amount - denoms[denomsLength - 1]);
    }
    // Driver code to test the above function
    public static void Main(string[] args)
    {
        int[] denoms = { 25, 10, 5, 1 };
        Console.WriteLine(CountChange(denoms, denoms.Length, 10));  // Output: 4
    }
}