Java递归回溯问题

Question

在这个递归回溯问题上遇到一些麻烦：

“编写一个方法可分区，它接受整数列表作为参数，并使用递归回溯来发现该列表是否可以分为两个总和相等的子列表如果给定的列表可以被平均划分，你的方法应该返回 true，否则返回 false。”

例如，列表 [1, 2, 3] 可以分为子列表 [1, 2] 和 [3]，因此它将产生“true”结果。

我的解决方案看起来是正确的，但无论如何都会返回 false。我不明白为什么。

public static boolean partitionable(List<Integer> list1) {
        List<Integer> list2 = new ArrayList<Integer>();
        return partitionable(list1, list2);
    }

public static boolean partitionable(List<Integer> list1, List<Integer> list2) {
    boolean finalAnswer = false;
    int sum1 = 0;
    int sum2 = 0;
    for (int i = 0; i < list1.size(); i++) {
        sum1 += list1.get(i);
    }
    for (int i = 0; i < list2.size(); i++) {
        sum2 += list2.get(i);
    }
    if (sum1 == sum2) {
        return true;
    } else {
        for (int i = 0; i < list1.size() - 1; i++) {
            int number = list1.remove(i);
            list2.add(number);
            finalAnswer = partitionable(list1, list2);
            list2.remove(list2.size() - 1);
            list1.add(i, number);
        }
    }
    return finalAnswer;
}

编辑：我修复了从 list1 中删除元素两次的问题。

Answer 1

您正在调用 list1.remove(i) 两次。这可能会扰乱您的算法，因为您要删除两个数字，并仅保存其中一个以添加到 list2 中。

如果它仍然不起作用，我还注意到您忽略了 list1 的最后一个元素作为转到 list2 的候选元素。我没有看到发生这种情况的算法原因：您应该尝试从 for 循环中删除 -1 。

Answer 2

问题是调用 list1.remove(i) 两次。这行不通。

您从 list1 中删除了两个数字，并将其保存到 list2 中时，仅保存了 1 个数字。

Answer 3

您的递归情况（else 块）应检查是否finalAnswer == true，如果是这种情况，则立即返回。否则，您将跳过它到返回 false 的情况，并最终在底部返回它。

这并不能解决整个问题，因为您还从 list1 中删除了一个项目两次。解决这两个问题应该会给你带来正确的解决方案。

Answer 4

抱歉，我没有直接回答你的问题，但我对所提出问题的理解需要不同的答案。

原来的问题是这样问的：
如果给定的列表可以平均分区，您的方法应该返回 true

并且您稍后声明这一点：
[1, 2, 3] 可以划分为子列表 [1, 2] 和 [3]，因此它会产生“true”结果。

这对我来说是不正确的。正确的解决方案（暂时忽略递归回溯要求）是否是计算整数元素的数量，% 2并返回NOT result？

换句话说：

List has three elements.  
Divide by 2, remainder 1.
Return 0, list is not equally dividable.

List has four elements.
Divide by 2, remainder 0.
Return 1, list is equally dividable.

请让我知道我在哪里误解了这个问题。