Finding ways to achieve a target sum using recursion

Question

I need your review and suggestions how to make this code better. I'm just learning recursion and sure that this solution is not ideal.

Question:

Write a function that given an input array of integers with a varying length input integers array, and the desired target_sum, returns the number of combinations, of any length, that add up to that target_sum.

EXAMPLE 1:

total_combinations = calculate_combinations([5, 5, 15, 10], target_sum=15)

ANSWER 1:

Should return 3, as there are 3 combinations of numbers from the input array that add up to 15, namely:

15 5+10 5+10 10

solution:

private static int mainfunction(int[] input, int target)
{
    int result = 0;
    for (int i = 0; i <= input.Length - 2; i++)
    {
        int temp = mainfunction_slave(input, i, target, 1);
        result = result + temp;
    }
    return result;
}
private static int mainfunction_slave(int[] input, int index, int target, int check)
{
    if ((index  + check) > (input.Length - 1))
        return 0;
    if ((input[index] + input[index + check]) == target || (input[index] == target))
        return mainfunction_slave(input, index, target, check + 1) + 1;
    return mainfunction_slave(input, index, target, check + 1);
}

• The task needs to be done via recursion, but if you have any other better solution, please let me know.

Answer 1

A couple of quick notes:

• Methods in C# should be named PascalCase.
• mainfunction isn't a great name. It should be named by what it does
• mainfunction_slave is also a bad name, you shouldn't use underscores in method names in C#

---

You need to plan your recursion:

1. What's the base case?
2. What can you make smaller/approach the base case as you go?

The base case is fairly trivial:

If the array has 1 element, return whether that element matches the target.

static int CalculateCombinations(int[] numbers, int target)
{
    // trivial solution:
    if (numbers.Length == 0)
    {
        return 0;
    }

    // base case:
    if (numbers.Length == 1)
    {
        return numbers[0] == target ? 1 : 0;
    }
}

Cool, we could now (or even before this) write a test or two:

[TestMethod]
public void CaclculateCombinationsWithSingleElement()
{
    var numbers = new[] { 1 };
    var target = 1;

    var result = YourClass.CalculateCombinations(numbers, target);

     Assert.AreEqual(1, result);
}

(I don't use MSTest myself so not sure if the above is 100% correct).

Now you need to think about how to split the problem up. Recursion on a list is almost always making the list smaller at each step.

The number of combinations is:

var count = 0;
for (var i = 0; i < numbers.Length; i++)
{
    // are we at a solution ?
    if (numbers[i] == target)
    {
        count++;
    }

    // find solutions that sum to the current target - the current number
    // on remainder of the array
    var subArray = numbers.Skip(i + 1).ToArray();
    count += CalculateCombinations(subArray, target - numbers[i]);
 }
 return count;

If you only consider positive integers, it looks like target is getting smaller too but actually only the numbers array is getting 'smaller' as negative numbers or 0s don't make target closer to 0.

That makes the whole solution something like:

static int CalculateCombinations(int[] numbers, int target)
{
    if (numbers.Length == 0)
    {
        return 0;
    }
    if (numbers.Length == 1)
    {
        return numbers[0] == target ? 1 : 0;
    }

    var count = 0;
    for (var i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] == target)
        {
            count++;
        }
        var subArray = numbers.Skip(i + 1).ToArray();
        count += CalculateCombinations(subArray, target - numbers[i]);
    }
    return count;
}

---

Update:

On reflection, the base case can simply be an empty array. We don't need to worry about the length = 1 case because it would have been counted in the for loop anyway.

That means the code can be simplified to:

static int CalculateCombinations(int[] numbers, int target)
{
        if (numbers.Length == 0)
        {
            return 0;
        }

        var count = 0;
        for (var i = 0; i < numbers.Length; i++)
        {
            if (numbers[i] == target)
            {
                count++;
            }
            var subArray = numbers.Skip(i + 1).ToArray();
            count += CalculateCombinations(subArray, target - numbers[i]);
        }
        return count;
    }

I'd recommend The Little Schemer as a great introduction to recursion. One of the commandments is:

Simplify only after the function is correct.

So I don't feel too bad about overcomplicating it the first time :)