Java递归回溯问题

Question

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

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

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

我的解决方案似乎是正确的，但无论如何都会返回 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。