没有循环的分区算法，只有递归

Question

给定一个整数列表。找出它是否可以分成两个和相等的子列表。列表中的数字未排序。

例如：
像 [1, 2, 3, 4, 6] 这样的列表将 return 为真，因为 2 + 6 = 1 + 3 + 4 = 8
像 [2, 1, 8, 3] 这样的列表将 return false。

我在一个在线练习平台上看到了这个问题。我知道如何使用 for 循环 + 递归来完成它，但是如何在没有循环（或迭代器）的情况下解决它？

Answer 1

思考这个问题的方法 尝试思考用什么方法可以将这个问题分解成相互依赖的小问题。首先想到的是按照索引拆分问题。让我们尝试从左到右（每次调用将索引增加 1）。我们的基本情况是在我们遍历所有元素之后，即数组的末尾。我们需要在那里做什么？将总和相互比较，因此我们需要传递它们。对于实际的递归调用，有两种可能性，一种是将当前元素添加到任一总和中。我们只需要检查这两个调用和 return true 如果一个 returned true.

这导致了一个没有任何循环的解决方案，方法是让你的递归函数将当前索引和两个总和作为参数，并有 2 个递归案例 - 一个你添加当前元素添加到一个总和，然后将其添加到另一个总和。然后在到达数组末尾时比较总和。

在 Java 中，它看起来像这样：

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]);
}

这可以通过仅传递 1 个和并对其进行加法或减法然后在最后与 0 进行比较来稍微改进。

请注意，这是 the partition problem 并且这个强力解决方案需要指数时间（即随着输入大小的增加，它会变得非常慢非常快）。

没有循环的分区算法，只有递归

Partition algorithm without loop, only recursion

algorithm

recursion

partitioning

depth-first-search

partition-problem