Partition algorithm without loop, only recursion

Question

Given a list of integers. Find out whether it can be divided into two sublists with equal sum. The numbers in the list is not sorted.

For example:
A list like [1, 2, 3, 4, 6] will return true, because 2 + 6 = 1 + 3 + 4 = 8
A list like [2, 1, 8, 3] will return false.

I saw this problem in an online-practice platform. I know how to do it with for loop + recursion, but how do I solve it with no loop (or iterator)?

Answer 1

The way to think about this it to try to think in which ways you can break up this problem into smaller problems which are dependent on each other. The first thing that comes to mind is to split the problem according to the index. Let's try just going from left to right (increase index by 1 with every call). Our base case would be after we've gone through all elements, i.e. the end of the array. What do we need to do there? Compare the sums with each other, so we need to pass those through. For the actual recursive call, there are 2 possibilities, those being the current element added to either sum. We just need to check both of those calls and return true if one returned true.

---

This leads to a solution without any loops by having your recursive function take the current index along with both sums as parameters, and having 2 recursive cases - one where you add the current element to the one sum, and one where you add it to the other sum. And then compare the sums when you get to the end of the array.

In Java, it would look like this:

boolean canBeDividedEqually(int[] array)
{
    return canBeDividedEquallyHelper(array, 0, 0, 0);
}

boolean canBeDividedEquallyHelper(int[] array, int i, int sum1, int sum2)
{
    if (i == array.length)
        return sum1 == sum2;
    return canBeDividedEquallyHelper(array, i+1, sum1 + array[i], sum2) ||
           canBeDividedEquallyHelper(array, i+1, sum1, sum2 + array[i]);
}

This can be improved slightly by only passing through 1 sum and either adding or subtracting from it and then comparing against 0 at the end.

Note that this is the partition problem and this brute force solution takes exponential time (i.e. it gets very slow very quickly as input size increases).