Javaの再帰的なバックトラックの問題

Question

は、この再帰的なバックトラッキングの問題といくつかの問題を持つ：

「のパラメータとしての整数のリストを受け取り、リストを2つに分割することができるかどうかを発見するために、再帰的なバックトラックを使用していますパーティション化方法を書きます指定されたリストを等しく分割できる場合は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; 
} 

EDIT：list1から要素を2回削除するという問題を修正しました。

Answer 1

list1.remove(i)を2回呼び出しています。 2つの数字を削除し、そのうちの1つだけを保存するとlist2に追加されるので、おそらくアルゴリズムが乱れるでしょう。

まだ機能していない場合は、list2に進む候補としてlist1の最後の要素を無視していることに気付きました。これが発生するアルゴリズムの理由はわかりません：forループから-1を削除してください。

Answer 2

問題はlist1.remove(i)を2回呼び出すことです。これは動作しません。

You'r list1から2つの数値を削除し、list2でそれを節約しながら、あなただけの1

Answer 3

あなたの再帰的なケース（elseブロック）を保存しているがfinalAnswer == trueかどうかを確認し、それはだ場合は、直ちにそれを返す必要がありますケース。それ以外の場合は、falseが返されたケースにスキップして、最終的にはその結果を返します。

list1から2回もアイテムを削除しているため、これで問題は解決しません。両方を修正すると、適切なソリューションが得られるはずです。

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. 

私は質問を誤解してきたところ私に知らせてください。