Java-Rekursion - Ausgabe von mehreren rekursiven Aufrufen

Question

Mein Code hier generiert alle Kombinationen (Wiederholung eingeschlossen) der Werte in candidates, so dass die Werte zum Ziel summieren. Dies ist meine Lösung für https://leetcode.com/problems/combination-sum/.

Ich bin ein wenig verwirrt darüber, warum muss ich die folgende Zeile von Code:

currentSet = new ArrayList<>(currentSet);

Dieses es im Wesentlichen machen wird, so dass currentSet eine private Variable für alle rekursiven Aufrufe ist. Andernfalls ist currentSet eine gemeinsam genutzte Variable, die die rekursiven Aufrufe gleichzeitig ändern und zu Problemen führen. Zum Beispiel, wenn die obige Anweisung aus dem Code weggelassen, combinationSum({1, 2}, 4) hat die folgende Ausgabe:

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

Das Array [1,2] offensichtlich summieren sich nicht auf 4. Kann jemand eine solide Erklärung liefern, warum dies Ereignis?

Auch gibt es irgendwelche Optimierungen, die ich tun könnte, damit mein Code vermeiden kann, doppelte, aber neu angeordnete Arrays, wie meine aktuelle Methode in Brute-Force-Sortierung und überprüfen, wenn in der HashSet enthalten führt zu sehr schlechten Komplexität.

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

Die Linie

currentSet = new ArrayList<>(currentSet); 

ist Java-Weg eine Kopie Konstruktor aufzurufen, das heißt Sie neue Arraylist erstellen, die zunächst alle Elemente aus der alten Liste. Die ursprüngliche Liste und die neue Liste sind jedoch unabhängig, sodass Änderungen in der neuen Liste nicht in die ursprüngliche Liste übernommen werden. Dies ist wichtig in Ihrem Algorithmus, weil dieser Zeilen:

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

Hier können Sie am Ende der Liste ein Element hinzufügen, um alle möglichen rekursive Kombinationen mit diesem Element zu finden, und es später zu entfernen mit einem anderen zu versuchen. Wenn Sie nicht eine Kopie der Liste in dem rekursiven Anruf würden, würden currentSet Variable verändert werden und die Linie

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

würde das Element nicht entfernen Sie vor dem rekursiven Aufruf hinzugefügt, aber ein anderes Element, das hinzugefügt wurde innerhalb einer Rekursion - vergessen Sie nicht, dass Sie Elemente innerhalb einer Rekursion sortieren, so dass die ursprüngliche Reihenfolge nicht immer erhalten bleibt. Das ist in Ihrem Beispiel passiert, als Sie den Kopierkonstruktor weggelassen haben.

Mögliche Optimierung

Was natürlich mir in den Sinn kommt, ist die anfängliche Anordnung der Kandidaten am Anfang zu sortieren, in der combinationSum Methode. Das Iterieren durch das sortierte Array vermeidet Duplikate und Sie müssen nicht nach doppelten Ergebnissen suchen.