recursion: cut array of integers in two parts of equal sum - in a single pass

Question

Using recursion, find an index that cuts an array in two parts so that both parts have equal sum. Cut means to cut like with a knife. All the cells with index <= to the result must be equal in their sum to the all the cells with index > to the result. No cells can be left off or be part of both sides. The arrays contains arbitrary integers (i.e. positives, negatives, and zeros). If there is no such index return `-1`. You are not allowed to allocate heap objects. You must do it in a single pass. You must do it with recursion (i.e. cannot use loop constructs). Can be in any language or pseudocode. Forgot to add this: You cannot modify the array

Accepted Answer

Here's a way to do it that takes advantage of Ruby's ability to return multiple values. The first value is the index for the split (if it exists), the second is the sum of each half (or the sum of the whole array if no split is found):

```
def split(arr, index = 0, sum = 0)
  return -1, arr[index] if index == arr.length - 1
  sum = sum + arr[index]
  i, tail = split(arr, index + 1, sum)

if i > -1
    return i, tail
  elsif sum == tail
    return index, sum 
  end
  return -1, arr[index] + tail
end
```

Calling it like this:

```
p split([1, 1, 2])
p split([1])
p split([-1, 2, 1])
p split([2, 3, 4])
p split([0, 5, 4, -9])
```

Results in this:

```
[1, 2]
[-1, 1]
[1, 1]
[-1, 9]
[0, 0]
```

EDIT:

Here's a slightly modified version to address onebyone.livejournal.com's comments. Now each index in the array is accessed only once:

```
def split(arr, index = 0, sum = 0)
  curr = arr[index]
  return -1, curr if index == arr.length - 1
  sum = sum + curr
  i, tail = split(arr, index + 1, sum)

if i > -1
    return i, tail
  elsif sum == tail
    return index, sum 
  end
  return -1, curr + tail
end
```

recursion: cut array of integers in two parts of equal sum - in a single pass

Solution

Problem

Related problems