Java再帰 - いくつかの再帰呼び出しからの出力

Question

私のコードは、candidatesの値のすべての組み合わせ（繰り返しを含む）を生成し、値が合計されるようにします。これはhttps://leetcode.com/problems/combination-sum/の解決策です。

は、私は次のコード行を含める必要がある理由について少し混乱しています：とcurrentsetは、すべての再帰呼び出しのためのプライベート変数であるように

currentSet = new ArrayList<>(currentSet);

これは、本質的にそれを行います。それ以外の場合、currentSetは、再帰呼び出しが同時に変更されて問題が発生する共有変数になります。上記のステートメントがコードから省略されている場合たとえば、 combinationSum({1, 2}, 4)は、次の出力があります。

[[1, 1, 2], [1, 1, 1, 1], [1, 2]] 

配列[1,2]、明らかに4にまとめるありませんこれは、なぜ誰もがソリッドな説明を提供することができますハプニング？

また、HashSetに含まれていれば、現在のブルートフォースソートとチェックの方法が非常に複雑になるため、私のコードでは重複して並べ替えられない配列を避けることができます。

public List<List<Integer>> combinationSum(int[] candidates, int target) { 
     Set<List<Integer>> returnSet = new HashSet<>(); 
     returnSet = combSum(candidates, target, 0, returnSet, new ArrayList<Integer>()); 
     return new ArrayList<>(returnSet); 
    } 

private Set<List<Integer>> combSum(int[] candidates, int target, int i, Set<List<Integer>> returnSet, 
    List<Integer> currentSet) { 
    currentSet = new ArrayList<>(currentSet); 
    if(i == target) { 
     Collections.sort(currentSet); 
     if(!returnSet.contains(currentSet)) { 
      returnSet.add(new ArrayList<Integer>(currentSet)); 
     } 
    } else if(i <= target){ 
     System.out.println("Current set: " + returnSet.toString()); 
     System.out.println("Current sum: " + i + " current target: " + target); 
     for(int a: candidates) { 
      if(i + a <= target) { 
       System.out.println("\tAdding: " + a + " so that the new sum will be: " + (i + a)); 
       currentSet.add(a); 
       returnSet = combSum(candidates, target, i + a, returnSet, currentSet); 
       currentSet.remove(currentSet.size() - 1); 
      } 
     } 
    } 

    return returnSet; 
} 

Answer 1

ライン

currentSet = new ArrayList<>(currentSet); 

はつまり、あなたが最初に古いリストからすべての要素を持つ新しいのArrayListを作成している、コピーコンストラクタを呼び出すためのJava-方法です。ただし、元のリストと新しいリストは独立しているため、新しいリストの変更は元のリストに反映されません。これは、これらのラインのあなたのアルゴリズムで重要である：

ここ

  currentSet.add(a); 
      returnSet = combSum(candidates, target, i + a, returnSet, currentSet); 
      currentSet.remove(currentSet.size() - 1); 

あなたは、リストの末尾に要素を追加し、その要素を持つすべての可能な再帰的な組み合わせを見つけて、別のものにしようとするために、後でそれを削除しています。あなたは再帰呼び出しでリストのコピーを作成しなかった場合は、currentSet変数が変更されるとライン

currentSet.remove(currentSet.size() - 1); 

あなたは、再帰呼び出しの前に追加された要素が、加えて他のいくつかの要素を削除しません再帰内では、再帰の中で要素をソートしていることを忘れないでください。元の順序は常に保持されるわけではありません。これは、コピーコンストラクタを省略したときのあなたの例で起こったことです。

自然combinationSum方法では、初めに候補者の最初の配列をソートすることである私の心に来る何可能な最適化

。ソートされた配列を反復することで重複が回避され、結果が重複していないかどうかを確認する必要はありません。