1

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

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

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

4

1 回答 1

2

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

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

在 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 进行比较来稍微改进。

请注意，这是分区问题，这种蛮力解决方案需要指数级的时间（即，随着输入大小的增加，它会变得非常缓慢）。

于 2017-05-11T22:50:09.687 回答