Finden von Teilmengen von Zahlen mit einer gegebenen Summe

Question

Mit Rekursion schreiben Sie ein Programm, das eine Liste von ganzen Zahlen und einer gegebenen Summe gibt, findet alle Teilmengen der Zahlen, deren Summe die gegebene Summe ist. Zählen Sie die Anzahl der gefundenen Teilmengen. Wenn keine Untergruppe vorhanden ist, sollten Sie angeben, dass keine Lösung gefunden wird. Zum Beispiel, da die Liste 6, 13, 3, 3, und die Summe ist 19, soll Ihr Programm findet zwei Lösungen:

6 + 13 = 19 
13 + 3 + 3 = 19 

begrenzen die Anzahl der ganzen Zahlen in der Eingabeliste auf maximal 20 Zahlen. Akzeptieren Sie nur positive ganze Zahlen und verwenden Sie 0, um das Ende der Liste zu markieren. Das folgende ist ein Probelauf:

Enter positive integers terminated with 0: 6 13 3 3 0 
Enter the desired sum: 19 
Solution 1:6 +13 =19 
Solution 2: 13 +3 +3 =19 
Found 2 solutions 

dies ist mein Code, aber es ist nur ein Untersatz zu finden, ich will alle Untersätze finden. irgendeine Hilfe?

public static boolean SubSetSum(int start, int[] nums, int target) { 
     if (start >= nums.length) { 
      return (target == 0); 
     } 
     if (SubSetSum(start + 1, nums, target - nums[start])) { 

      System.out.println(nums[start]); 
      return true; 
     } 
     if (SubSetSum(start + 1, nums, target)) { 

      return true; 
     } 
     return false; 

    } 




    public static void main(String[] args) { 

     int[] mySet = {4,1,3,2}; 
     int sum = 5; 
     System.out.println("The Goal is : " + sum); 

     SubSetSum(0,mySet, sum) ; 
    } 
} 

Answer 1

Das grundlegende Problem ist, dass Sie die falsche Information zurückgegeben haben: Sie müssen alle gefundenen Lösungen, aber Sie haben nach nur einen boolean zurück, ob Sie erfolgreich. Stattdessen müssen Sie eine Lösungsliste erstellen.

Fälle Basis:

• wenn target = 0, gelang es Ihnen. Drucken Sie die Lösung und inkrementieren Sie den Zähler.
• sonst, wenn Ziel < 0, scheiterte.
• Wenn Sie keine Artikel mehr haben, ist der Fehler aufgetreten.

Rekursion Fälle:

Sie auf der Grundidee sind in Ordnung: wiederholen sowohl mit als auch ohne die aktuelle Nummer abgezogen wird. Sie können jedoch auch eine Liste der in diesem Zweig verwendeten Nummern eingeben. Auf diese Weise können Sie beim Drucken die Liste ausdrucken. Es gibt andere Möglichkeiten, diesen Schritt zu behandeln, aber ich denke, das ist am einfachsten für Ihre Anwendung. Wenn Sie die Signatur von SubSetSum nicht ändern dürfen, verwenden Sie diese als "Wrapper" und rufen Sie von dort aus Ihre eigentliche Funktion auf, beginnend mit einer leeren Liste.

Bewegt Sie das? Sie können auch die Dutzende von vorherigen Fragen zu diesem Problem überprüfen.

Answer 2

Ihre Hauptthemen sind, dass Sie:

• kehren sofort, sobald Sie die Lösung
• finden Zahlen nur erwägen, aus für Ihre Lösung

links nach rechts

Was Sie brauchen, um Beachten Sie alle möglichen Unterlisten der ursprünglichen Liste für Ihre Lösung, z. B. für eine Liste von [A, B, C, D], die Lösung kann [A, C, D] sein. Ein guter Ausgangspunkt ist ein Code, mit dem alle Unterlisten einer Liste erstellt werden können. Um dies zu tun, benötigen Sie eine Reihe von Listen, in denen Sie alle Möglichkeiten zusammenfassen können. Hier ist ein Beispiel, das dies tut, indem Elemente aus einer Kopie der ursprünglichen Liste zu entfernen, aber es gibt viele Möglichkeiten, dies zu tun:

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 

class ResursionTest { 
    public static void findSubsets(Set<List<Integer>> allSubsets, List<Integer> nums) { 
     if (nums.size() == 0) { 
      return; 
     } 

     // add the current list as a possibility 
     allSubsets.add(new ArrayList<>(nums)); 

     // then add a possibility that has one less 
     for (int i = 0; i < nums.size(); i++) { 
      final List<Integer> subset = new ArrayList<>(nums); 
      subset.remove(i); 
      findSubsets(allSubsets, subset); 
     } 
    } 


    public static void main(String[] args) { 
     final Integer[] array = {4, 1, 3, 2}; 
     final HashSet<List<Integer>> allSubsets = new HashSet<>(); 

     findSubsets(allSubsets, Arrays.asList(array)); 
     System.out.println(allSubsets); 
    } 
} 

Wenn Sie dies ausführen, können Sie durch die Ausgabe sehen, dass wir alle sind zu finden die Unterlisten der ursprünglichen Eingabeliste [4, 1, 3, 2].

Ausgangsprüfung:

[[3, 2], [1], [4, 3], [2], [3], [1, 2], [4, 3, 2], [1, 3], [4], [4, 1, 2], [4, 1, 3], [4, 1, 3, 2], [4, 1], [1, 3, 2], [4, 2]] 

Dann alles, was übrig bleibt, ist nur Teil-Listen hinzufügen, die zu der gewünschten Zahl addieren, anstatt alle Möglichkeiten des Hinzufügens.

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 

class ResursionTest { 
    public static void findSubsets(Set<List<Integer>> allSubsets, List<Integer> nums, int sum) { 
     if (nums.size() == 0) { 
      return; 
     } 

     int currentSum = 0; 
     for (Integer num : nums) { 
      currentSum += num; 
     } 

     // does the current list add up to the needed sum? 
     if (currentSum == sum) { 
      allSubsets.add(new ArrayList<>(nums)); 
     } 

     for (int i = 0; i < nums.size(); i++) { 
      final List<Integer> subset = new ArrayList<>(nums); 
      subset.remove(i); 
      findSubsets(allSubsets, subset, sum); 
     } 
    } 


    public static void main(String[] args) { 
     int sum = 5; 
     final Integer[] array = {4, 1, 3, 2}; 
     final HashSet<List<Integer>> allSubsets = new HashSet<>(); 

     findSubsets(allSubsets, Arrays.asList(array), sum); 
     System.out.println(allSubsets); 
    } 
} 

Antwort-Check:

[[3, 2], [4, 1]] 

Es gibt einige Optimierungen Sie noch mit diesem Code machen kann, die ich Ihnen überlassen wird.