Dado um vetor com 'n' números distintos, calcular quantas possibilidades existem para se obter a soma 's'

CountSumRecursively.cs

// Exemplo para se obter soma igual a 16 para os números 1, 2 e 5
static void Main(string[] args)
{
    var startTime = DateTime.Now;
    var count = CountSum(new[] { 1, 2, 5 }, 16);
    var elapsedTime = DateTime.Now - startTime;

    Console.WriteLine(string.Format("Sum count: {0}", count));
    Console.WriteLine(string.Format("Executed in: {0} ms", elapsedTime.TotalMilliseconds));
    Console.ReadKey(true);
}

private static int CountSum(int[] numbers, int expectedResult)
{
    return CountSumRecursively(numbers, 0, expectedResult, 0);
}

private static int CountSumRecursively(int[] numbers, int currentResult, int expectedResult, int numberIndex)
{
    if (currentResult == expectedResult)
        return 1;

    if ((currentResult > expectedResult) || (numberIndex >= numbers.Length))
        return 0;

    return CountSumRecursively(numbers, currentResult + numbers[numberIndex], expectedResult, numberIndex) +
            CountSumRecursively(numbers, currentResult, expectedResult, numberIndex + 1);
}

CountSumWithLoop.cs

// Exemplo para se obter soma igual a 16 para os números 1, 2 e 5
static void Main(string[] args)
{
    var startTime = DateTime.Now;
    var count = CountSum(new[] { 1, 2, 5 }, 16);
    var elapsedTime = DateTime.Now - startTime;

    Console.WriteLine(string.Format("Sum count: {0}", count));
    Console.WriteLine(string.Format("Executed in: {0} ms", elapsedTime.TotalMilliseconds));
    Console.ReadKey(true);
}

private static int CountSum(int[] numbers, int expectedResult)
{
    return CountSumWithLoop(numbers, 0, expectedResult, 0);
}

// Demora o dobro do tempo se comparado com o método recursivo
private static int CountSumWithLoop(int[] numbers, int currentResult, int expectedResult, int numberIndex)
{
    if (currentResult == expectedResult)
        return 1;

    if ((currentResult > expectedResult) || (numberIndex >= numbers.Length))
        return 0;


    var sumCount = 0;
    var loopCount = expectedResult/numbers[numberIndex];

    for (var i = 0; i <= loopCount; i++)
    {
        var loopResult = currentResult + i*numbers[numberIndex];
        sumCount += CountSumWithLoop(numbers, loopResult, expectedResult, numberIndex + 1);
    }

    return sumCount;
}

em scala: https://gist.github.com/3781896