1

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

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

例如，列表 [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 中删除元素两次的问题。

4

4 回答 4

4

你打list1.remove(i)了两次电话。这可能会弄乱您的算法，因为您要删除两个数字，并且只保存其中一个以添加到list2.

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

于 2011-07-25T01:30:01.670 回答
1

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

您从 中删除两个数字list1，同时将其保存在 中list2，您只保存 1。

于 2011-07-25T01:30:31.913 回答
1

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

这并不能解决整个问题，因为您还要从list1两次中删除一个项目。解决这两个问题应该可以为您提供正确的解决方案。

于 2011-07-25T01:31:25.000 回答
0

请原谅我没有直接回答你的问题，但我对所提出问题的理解需要一个不同的答案。

原来的问题是这样问的：
Your method should return true if the given list can be partitioned equally

你后来声称：
[1, 2, 3] can be partitioned into the sublists [1, 2] and [3], so it would produce a result of "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.

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

于 2011-07-25T01:38:42.940 回答