um eine Teilmenge aus einer Menge zu finden, deren Summe gleich Null ist?

Question

Ich habe eine Reihe von ganzen Zahlen wie diese

{1,4,5,2,7,8,-3,-5,-6,9,3,-7,-1,5,6} 

die Menge beliebige Anzahl von Elementen enthält, kann als Eingabe vom Benutzer genommen brauche ich alle möglichen Teilmengen aus dieser Reihe, deren Summe gleich Null ist beispielsweise zu finden in Dieser Fall in dem obigen Satz werden die Teilmengen

{(1,2, -3)}

{(1, -1)}

{(3, -3)} sein

{(5, -5)}

etc etc

ich diesen Code versucht, aber es kehrt mir nicht antworten, wenn ich target gleich Null setze.

import java.util.ArrayList; 
import java.util.Arrays; 

class SumSet { 

    static void sum_up_recursive(ArrayList<Integer> numbers, int target, 
           ArrayList <Integer> partial) 
    { 
     int s=0; 
     for (int x: partial) s += x; 
     if (s == target) 
      System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target); 

     if (s >= target) 
      return; 

     for(int i=0;i<numbers.size();i++) { 
      ArrayList<Integer> remaining = new ArrayList<Integer>(); 
      int n = numbers.get(i); 
      for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j)); 
      ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial); 
      partial_rec.add(n); 
      sum_up_recursive(remaining,target,partial_rec); 
     } 
    } 

    static void sum_up(ArrayList<Integer> numbers, int target) 
    { 
     sum_up_recursive(numbers,target,new ArrayList<Integer>()); 
    } 

    public static void main(String args[]) { 
     Integer[] numbers = {3,4,6,4,5,2,6}; 
     int target = 9; 
     sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target); 
    } 
} 

Answer 1

Ich stieß auf dieses Problem in meinen College-Tagen bei Google-Interview und löste es in sehr langer Zeit.

Denken Sie darüber nach, für eine Menge, 0 zu sein, dort "muss" negative Zahl sein und dort "muss eine Menge positiver Zahl sein".

Schritte:

1. Created a 2 arrays negativeNumArrays and POsitiveNumArrays 
2. Create a new negative set(does not allows duplicate) which is possible sums of  negative arrays ex - 
    [-1,-2,-3] = [-1,-2,-3, {-1-2=3},{-1,-3=-4},{-2,-3=-5},{-6}] = [-1,-2,-3,-4,-5,-6] 
So the set looked like 
Key:Value 
"1" =-1 
"2" = -2 
... 
"2:3"=-5 
"1:2:3"=-6 

Here 
"N6" = -6 

3. For this new set of negative array find combination in positive 
    array which matches any of the 6 negative arrays. 

Same as above say positive numbers are 3 and 4 
So the set would look like 
"3"=3 

"4"=4 

"3:4"=7 


Now simple compare the two sets and see which of these are equal 
So for example Negative Set "1:3" = Positive Set "4" 
and hence use Stringtokenizer to get the numbers from set key {-1,-3,4} 

Answer 2

Du bist gerade nicht, wenn partial leer ist, in welchem ​​Fall sum_up_recursive() sofort beim ersten Versuch zurück, wenn target == 0 try this:

if (partial.size() > 0) { 
    for (int x : partial) 
     s += x; 

    if (s == target) 
     System.out.println("sum(" + Arrays.toString(partial.toArray()) + ")=" + target); 

    if (s >= target) 
     return; 
} 

Beachten Sie, dass es andere Möglichkeiten gibt, den von Ihnen verwendeten Algorithmus erheblich zu verbessern. Ich beantworte nur, warum Ihr Code nicht wie erwartet funktioniert.

Answer 3

Hier ist ein Lösungsvorschlag.

Ich löse zuerst ein erstes Teilproblem: Ich nehme an, dass alle Zahlen und das Ziel positive Zahl sind, dann löse ich das wirkliche Problem.

Um dies zu erreichen, zerlege ich das Problem im Grunde in Teilprobleme.

Beginnen wir mit einem Beispiel illustrieren:

Zahlen: 1,3,8,2,7 Ziel: 10

Erstens: sortieren Sie die Liste: Zahlen: 8,7,3,2,1 Ziel: 10 Dann rekursiv die Lösungen zu den folgenden Problemen finden:

Numbers: 7,3,2,1 target: 10-8 = 2

Numbers: 3,2,1 target: 10-7 = 3

Zahlen: 2,1 Target: 10-3 = 2

Zahlen: 1 Target: 10-1 = 9

Ziel vor große Zahlen des Vergebens schnell Lösungen zu beseitigen, diese Nummer einschließlich (weil die Summe überschreitet schnell das Ziel). Hier

ist der kommentierten Code für die Auflösung dieses Teilproblem:

import java.util.ArrayList; 
import java.util.List; 

public class Problem { 

    /* 
    * Used at the end to recompose the solutions. 
    * This value is null for the root problem. 
    */ 
    private Integer nodeValue; 

    //The POSITIVE target sum 
    private int target; 

    //List of POSITIVE numbers, supposed to be sorted 
    private List<Integer> numbers; 

    private List<Problem> listSubProblems; 

    /* 
    * Link to the parent problem. 
    * Useful at the end to generate the results. 
    */ 
    private Problem parentProblem; 

    public Problem(int target, List<Integer> numbers, Integer nodeValue, Problem parentProblem){ 
     this.target=target; 
     this.numbers=numbers; 
     this.nodeValue=nodeValue; 
     this.parentProblem=parentProblem; 
     this.listSubProblems =new ArrayList<Problem>(); 
    } 

    public void solve(){ 
     buildSubProblems(); 
     for(Problem problem : listSubProblems){ 
      problem.solve(); 
     } 
    } 

    /** 
    * Builds a List of sub problems. 
    * For example, if {@link #numbers} contains 9 8 5 3, with target 10 
    * this method will return the following sub problems: 
    * 
    * <table> 
    *  <tr> 
    *   <td>nodeValue</td><td>target</td><td>numbers</td> 
    *  </tr> 
    *  <tr> 
    *   <td>9</td><td>10-9=1</td><numbers>8 5 3</numbers> 
    *  </tr> 
    *  <tr> 
    *   <td>8</td><td>10-8=2</td><numbers>5 3</numbers> 
    *  </tr> 
    *  <tr> 
    *   <td>5</td><td>10-5=5</td><numbers>3</numbers> 
    *  </tr> 
    * 
    * </table> 
    * 
    */ 
    private void buildSubProblems(){ 

     int numbersSize=numbers.size(); 

     /* 
     * Numbers are supposed to be positive so if the target is negative, 
     * there is no chance to find a valid solution. 
     * As the list of numbers is sorted, the case when target < 0 happens quickly 
     * Hence, it quickly removes combinations implying big numbers 
     */ 
     if(target>=0 && numbersSize> 1){ 

      for(int i=0;i<numbersSize;i++){ 
       Integer nodeValue=numbers.get(i); 
       List<Integer> subList=numbers.subList(i+1,numbersSize); 
       int newTarget=this.target-nodeValue; 
       Problem problem=new Problem(newTarget, subList, nodeValue, this); 
       System.out.println("Created problem: "+problem.dump()); 
       this.listSubProblems.add(problem); 
      } 
     } 
    } 

    /** 
    * @return True is the Problem contains exactly one number and that number equals the target. 
    */ 
    public boolean isNodeSolution(){ 
     return this.target==0; 
    } 

    public Integer getNodeValue(){ 
     return this.nodeValue; 
    } 

    public List<Problem> getListSubProblems(){ 
     return this.listSubProblems; 
    } 

    public Problem getParentProblem(){ 
     return this.parentProblem; 
    } 

    public String dump(){ 
     StringBuilder sb=new StringBuilder(); 
     sb.append("{nodeValue: "+this.nodeValue); 
     sb.append("; target: "+target); 
     sb.append("; numbers:"); 
     for(Integer integer : numbers){ 
      sb.append(integer+","); 
     } 
     sb.append("}"); 
     sb.append("Valid? : "+ isNodeSolution()); 
     return sb.toString(); 
    } 

} 

Hier ist der Code, der zeigt, wie es testen:

import java.util.Arrays; 
import java.util.Collections; 
import java.util.List; 

public class Main { 

    public static void main(String[] args) throws Exception{ 
     Integer numbers[]={1,3,8,2,7}; 
     int target=10; 

     List<Integer> listNumbers= Arrays.asList(numbers); 

     Collections.sort(listNumbers); 
     Collections.reverse(listNumbers); 

     //Build the root problem 
     Problem problem=new Problem(target,listNumbers,null,null); 

     //Solve it 
     problem.solve(); 

     //Dump the result. 
     dumpResult(problem); 

     System.out.println("Done!"); 
    } 

    private static void dumpResult(Problem problem){ 
     for(Problem p:problem.getListSubProblems()){ 
      if(p.isNodeSolution()){ 
       System.out.print("\nSolution :"); 
       dumpSolution(p); 
      } 
      dumpResult(p); 
     } 
    } 

    private static void dumpSolution(Problem problem){ 
     //If the current node is not the root problem 
     if(problem.getParentProblem()!=null){ 
      System.out.print(problem.getNodeValue() + ", "); 
      dumpSolution(problem.getParentProblem()); 
     } 
    } 
} 

Und hier ist ein Beispiel für Ausgang :

Created problem: {nodeValue: 8; target: 2; numbers:7,3,2,1,}Valid? : false 
Created problem: {nodeValue: 7; target: 3; numbers:3,2,1,}Valid? : false 
Created problem: {nodeValue: 3; target: 7; numbers:2,1,}Valid? : false 
Created problem: {nodeValue: 2; target: 8; numbers:1,}Valid? : false 
Created problem: {nodeValue: 1; target: 9; numbers:}Valid? : false 
Created problem: {nodeValue: 7; target: -5; numbers:3,2,1,}Valid? : false 
Created problem: {nodeValue: 3; target: -1; numbers:2,1,}Valid? : false 
Created problem: {nodeValue: 2; target: 0; numbers:1,}Valid? : true 
Created problem: {nodeValue: 1; target: 1; numbers:}Valid? : false 
Created problem: {nodeValue: 3; target: 0; numbers:2,1,}Valid? : true 
Created problem: {nodeValue: 2; target: 1; numbers:1,}Valid? : false 
Created problem: {nodeValue: 1; target: 2; numbers:}Valid? : false 
Created problem: {nodeValue: 2; target: -2; numbers:1,}Valid? : false 
Created problem: {nodeValue: 1; target: -1; numbers:}Valid? : false 
Created problem: {nodeValue: 2; target: 5; numbers:1,}Valid? : false 
Created problem: {nodeValue: 1; target: 6; numbers:}Valid? : false 

Solution :2, 8, 
Solution :3, 7, Done! 

Nun, dies deckt nicht das anfängliche Problem, das negative Zahlen impliziert. Um diesen Fall zu lösen, isoliere alle negativen Zahlen und berechne alle Kombinationen negativer Zahlen mit ihrer Summe.

Dann wird für jede Summe negative Zahl, erstellen Sie ein Teilproblem nur positive Zahlen und ein entsprechendes Ziel (ursprüngliche Ziel - Summe der negativen Zahlen), die

Ein Weg, um es zu verbessern: Die Komplexität der Probleme hängt auf die Anzahl der Kombinationen von negativen Zahlen. Wenn also mehr negative als positive Zahlen vorhanden sind, können Sie einfach alle Werte invertieren und das Invertierungsproblem lösen.

Eine andere Möglichkeit, es zu verbessern: Sie können die Summe der positiven Zahlen jedes Teilproblems im Speicher behalten. Wenn sum + nodeValue < Ziel ist, dann ist es nutzlos, den Zweig weiter zu erkunden.