Java рекурсивная проблема возврата

Question

Возникли проблемы с рекурсивной проблемой возврата:

"Напишите метод partitionable , который принимает список целых чисел в качестве параметра и использует рекурсивный возврат, чтобы определить, можно ли разделить список на два подсписка равной суммы. Ваш метод должен возвращать true, если данный список может быть разделен поровну, а если нет - false. "

Например, список [1, 2, 3] можно разбить на подсписки [1, 2] и [3], так что он выдаст результат «true».

Мое решение кажется правильным, но возвращает ложь, несмотря ни на что. Я не понимаю почему.

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

РЕДАКТИРОВАТЬ: я исправил проблему удаления элемента из списка1 дважды.

Answer 1

Вы звоните list1.remove(i) дважды. Это, вероятно, испортит ваш алгоритм, потому что вы удаляете два числа и сохраняете только одно из них, чтобы добавить к list2.

Если он все еще не работает, я также заметил, что вы пренебрегаете последним элементом list1 в качестве кандидата для перехода на list2. Я не вижу алгоритмической причины для этого: попробуйте удалить -1 из вашего for цикла.

Answer 2

Ваш рекурсивный регистр (блок else) должен проверить, если finalAnswer == true, и немедленно вернуть его, если это так. В противном случае вы пропустите его в случаях, когда возвращается false, и в конце концов вернете его внизу.

Это не решит всей проблемы, поскольку вы также дважды удаляете элемент из list1. Исправление обоих должно дать вам правильное решение.

Answer 3

Проблема состоит в том, чтобы вызвать list1.remove(i) дважды. Это не сработает.

Вы удаляете два числа из list1 и, сохраняя его в list2, вы сохраняете только 1.

Answer 4

Извините, что не отвечаю на ваш вопрос напрямую, но мое понимание поставленного вопроса требует другого ответа.

Оригинальный вопрос:
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.

Пожалуйста, дайте мне знать, где я неправильно понял вопрос.