per trovare un sottoinsieme da un insieme la cui somma è uguale a zero?

Question

Ho una serie di numeri interi come questo

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

il set può contenere qualsiasi numero di elementi come input è preso da parte dell'utente ho bisogno di trovare tutti i possibili sottoinsiemi di questa serie la cui somma è pari a zero, per esempio in questo caso nel set sopra i sottoinsiemi sarà

{(1,2, -3)}

{(1, -1)}

{(3, -3)}

{(5, -5)}

etc etc

Ho provato questo codice, ma non sta tornando a rispondere quando mi pongo target uguale a zero.

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

mi sono imbattuto in questo problema in tempi dell'università durante il colloquio di Google e risolto in un modo molto lungo.

Pensateci, poiché un set è 0, "deve" essere un numero negativo e lì "deve essere un insieme di numeri positivi".

Passi:

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

Non sta verificando se partial è vuota, nel qual caso sum_up_recursive() ritorna immediatamente al primo tentativo, quando target == 0. Prova questo:

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; 
} 

Nota, potrebbero esserci altri modi per migliorare notevolmente l'algoritmo che stai utilizzando. Sto solo rispondendo perché il tuo codice non funziona come previsto.

Answer 3

Ecco una proposta di soluzione.

Prima risolvo un primo sotto-problema: suppongo che tutti i numeri e l'obiettivo siano numeri positivi, quindi risolvo il problema reale.

Per ottenere ciò, fondamentalmente scompongo il problema nei sotto-problemi.

Illustriamo con un esempio:

Numeri: 1,3,8,2,7 di destinazione: 10

Primo: ordinare l'elenco: Numbers: 8,7,3,2,1 obiettivo: 10 Quindi trovare in modo ricorsivo le soluzioni ai seguenti problemi:

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

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

Numeri: 2,1 bersaglio: 10-3 = 2

Numeri: 1 porta: 10-1 = 9

Lo scopo di porre grandi numeri prima è quella di eliminare rapidamente soluzioni tra questo numero (perché la somma supera rapidamente l'obiettivo).

Ecco il codice commentato per la risoluzione di questo sub-problema:

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(); 
    } 

} 

Ecco il codice che mostra come testare esso:

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()); 
     } 
    } 
} 

E qui è un esempio di uscita :

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! 

Ora, questo non copre il problema iniziale che implica i numeri negativi. Per risolvere questo caso, isolare tutti i numeri negativi e calcolare tutte le combinazioni di numeri negativi, con la somma.

Quindi, per ogni somma di un numero negativo, creare un problema secondario contenente soltanto numeri positivi e un target corrispondente (obiettivo iniziale - somma dei numeri negativi)

Un modo per migliorarla: La complessità dei problemi dipende sul numero di combinazioni di numeri negativi. Quindi, se ci sono più numeri negativi che numeri positivi, puoi semplicemente invertire tutti i valori e risolvere il problema invertito.

Un altro modo per migliorarlo: è possibile mantenere in memoria la somma dei numeri positivi di ciascun sotto-problema. Se sum + nodeValue < target, allora è inutile continuare ad esplorare il ramo.