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

Answer 1

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

Answer 2

Iterating with recursion is a trivial transformation, so we'll assume you know how to do that.

If you use your "one pass" to build your own array of "sum to this index", and can make another pass on that array, I could see how to do it. Just iterate through that second array and subtract sum[x] from sum[last]. If you ever find a situation where the result = sum[x] you return x. If you don't then return -1.

As Neil N mentioned, if you define "pass" very loosely for recursion, such that the entire recursion can actually visit indices multiple times, then you could dispense with the second array.

---

After thinking about this a bit, I suspect the idea is to get you to only visit every array element once (in order), and to use recursion's built-in stack property to get rid of the need for any second array.

What you do is write your recursive routine to save off it's current index's array value in a local, add that value to a passed in "sum_of_array" value, then call itself on the next highest index (if there is one). If there isn't a next highest index, it saves the sum into a global, which is now available to every stacked recursive call. Each routine finishes by checking its sum against the global sum. If it is half, then it returns its index. Otherwise it returns -1. If a non -1 was returned from a call to itself, this last step is skipped and that value is returned. I'll show in pseudo-Ada

Total_Sum : integer;

function Split (Subject : Integer_Array; After : Integer := 0; Running_Sum : Integer := 0) is
begin
   Running_Sum := Running_Sum + Subject(After);
   if (After < Subject'last) then --'// comment Hack for SO colorizer
      Magic_Index : constant Integer := Split (Subject, After +  1, Running_Sum);
      if (Magic_Index = -1) then
         if (Total_Sum - Running_Sum = Running_Sum) then
            return After;
         else
            return -1;
         end if;
      else
         return Magic_Index;
      end if;
   else
      Total_Sum := Running_Sum;
      return -1;
   end if;
end Split;

This code should have the properties that:

• Calling it with just an array will return the described "split" index, or -1 if there isn't one.
• It only reads from any element in the source array once
• It reads the source array elements in strict index order.
• No extra structured data storage (array) is required.