递归:在两个相等和的部分中切割整数数组 - 在一次传递中

Question

使用递归,找到一个将数组分成两部分的索引,这样两个部分的总和相等.

切割意味着用刀切割.索引<=到结果的所有单元格的总和必须等于所有索引>到结果的单元格.没有细胞可以被遗弃或成为两侧的一部分.

数组包含任意整数(即正数,负数和零).

如果没有这样的索引返回-1.

您不能分配堆对象.

你必须一次性完成.

你必须使用递归(即不能使用循环结构).

可以是任何语言或伪代码.

忘了添加:你不能修改数组

Answer 1

这是一种利用 Ruby 返回多个值的能力的方法。第一个值是分割的索引（如果存在），第二个值是每一半的总和（如果没有找到分割，则为整个数组的总和）：

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

像这样调用它：

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

结果如下：

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

编辑：

这是一个稍作修改的版本，用于解决 onebyone.livejournal.com 的评论。现在数组中的每个索引仅被访问一次：

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