Java的遞歸回溯問題

Question

遇到一些麻煩這個遞歸回溯問題：

「寫的方法分區接受整數作爲參數的列表，並使用遞歸回溯，發現清單是否可以被劃分爲兩個如果給定列表可以被平等分割，那麼你的方法應該返回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; 
} 

編輯：我解決了從列表1中刪除元素兩次的問題。

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

對不起，我沒有直接回答你的問題，但我對提出的問題的理解需要不同的答案。

原來的問題問這樣的：
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. 

請讓我知道我誤解了這個問題。