同じ番号を使用する組み合わせを含む、リュージョンを使用してリストからすべての組み合わせを取得する

Question

私は数字のリスト：[10, 13, 15]を持っています。私は現在、私は、再帰的な方法で持ってまで追加または28

の目標よりも小さい、リスト内の数字の組み合わせを見つけようとしています：

public void combinations(ArrayList<Integer>data,int fromIndex, int endIndex) 
{ 
    int sum = 0; 
    int target = 28; 
    ArrayList<Integer>results = new ArrayList<Integer>(); 
    if(fromIndex == endIndex) 
    { 
     return; 
    } 

    for(int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) 
    { 
     if(sum + data.get(currentIndex) <= target) 
     { 
      results.add(data.get(currentIndex)); 
      sum +=data.get(currentIndex); 
     } 

    } 

    System.out.println(results); 
    combinations(data, fromIndex + 1, endIndex); 
} 

を現在、これは出力： [10, 13],[13, 15],[15]たが私の再帰的なメソッドが+1であるので、なぜ私はこれらのソリューションを得ているのか理解しています。しかし、[10],[13],[10,10]などの他のソリューションは含まれていませんし、私はこれを実装する方法を考えていましたが、私の再帰的メソッドで増分を変更する必要がありますか？

Answer 1

public static void combinations(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> ans, int startIndex, int endIndex, int sum) { 

    if(startIndex > endIndex) { 
     for(ArrayList<Integer> x : ans) { 
      System.out.println(x); 
     } 
     return; 
    } 
    ArrayList<Integer> newTemp; 
    ArrayList<ArrayList<Integer>> newAns = new ArrayList<ArrayList<Integer>>(); 
    for(ArrayList<Integer> x : ans) { 
     newAns.add(x); 
    } 
    for(ArrayList<Integer> x : ans) { 
     int s = 0; 
     newTemp = new ArrayList<Integer>(); 
     for(Integer v : x) { 
      newTemp.add(v); 
      s+=v; 
     } 
     if(s + arr.get(startIndex) <= sum) { 
      newTemp.add(arr.get(startIndex)); 
      newAns.add(newTemp); 
     } 
    } 

    if(arr.get(startIndex) <= sum) { 
     newTemp = new ArrayList<Integer>(); 
     newTemp.add(arr.get(startIndex)); 
     newAns.add(newTemp); 
    } 

    combinations(arr,newAns, startIndex+1, endIndex, sum); 
} 

私はあなたのコードを考えることができませんでしたので、コードを書き直さなければなりません。

第2に、私は最初に直面していたConcurrentModificationExceptionを避けるために常にnewArrayListを作成しなければならず、後でそれについての知識を得てから克服するでしょう。

さて、この方法は

public static void main (String[] args) { 
    ArrayList<Integer> arr = new ArrayList<Integer>(); 
    arr.add(10); 
    arr.add(15); 
    arr.add(13); 
    arr.add(-5); 
    arr.add(28); 
    combinations(arr, new ArrayList<ArrayList<Integer>>(), 0, 4, 28); 
} 

説明と呼ばれるべきである：私は、int型の範囲内の任意の金額を合わせて、あなたの質問の答えを一般化しています。 私は、ArrayListのArrayListを作成しました。これは、すべての組み合わせをベースケースで印刷します。

1. 私は、現在の要素が< = sumの場合は、最初の要素、つまり現在の要素を含むArrayListを最初に追加しました。
2. 残りのすべてのArrayListについて、それぞれの合計を計算し、前のArrayListに現在の要素を追加することで上記の条件が満たされているかどうかを確認しました。
3. 同時に、新しいArrayListを作成し、各ArrayListの合計を計算している間にすべての要素をコピーした後、2番目のケースが良好であれば、現在の要素をtemp ArrayListに追加し、temp ArrayListをAnswer ArrayListのArrayListです。
4. 次に、startIndexを1ずつインクリメントして再帰を呼び出しました。