найти подмножество из множества, сумма которого равна нулю?

Question

У меня есть набор целых чисел, как этот

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

набор может содержать любое количество элементов в качестве входных данных берется от пользователя, мне нужно, чтобы найти все возможные подмножества из этого множества, сумма которых равна нулю, например, в этот случай в приведенном выше наборе подмножества будет

{(1,2, -3)}

{(1, -1)}

{(3, -3)}

{(5, -5)}

и т.д. и т.п.

Я попробовал этот код, но он не возвращает мне ответ, когда я устанавливаю target равным нулю.

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

Я столкнулся с этой проблемой в мои дни колледжа в интервью Google и решил ее очень долго.

Подумайте об этом, так как набор 0 будет иметь «отрицательное» число, и там «должно быть множество положительного числа».

Шаги:

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

Вы не проверять, если partial пуст, в этом случае sum_up_recursive() будет немедленно вернуться с первой попытки, когда target == 0. Попробуйте это:

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

Обратите внимание, что могут быть другие способы значительно улучшить алгоритм, который вы используете. Я просто отвечаю, почему ваш код работает не так, как ожидалось.

Answer 3

Вот предложение решения.

Сначала я решил первую проблему: я полагаю, что все числа и цель являются положительным числом, тогда я решаю реальную проблему.

Для этого я в основном разлагаю проблему в подзадачах.

Проиллюстрируем на примере:

Numbers: 1,3,8,2,7-мишени: 10

Первый: сортировать список: Numbers: 8,7,3,2,1 Цель: 10 Затем найти рекурсивно решения следующих проблем:

Numbers: 7,3,2,1 цели: 10-8 = 2

Число: 3,2,1 цели: 10-7 = 3

номера: 2,1-мишени: 10-3 = 2

Числа: 1 мишень: 10-1 = 9

Целью размещения больших чисел перед, чтобы быстро устранить решения, включая этот номер (поскольку сумма быстро превышает целевую).

Вот прокомментировал код для решения этой подпрограммы задачи:

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

} 

Вот код, который показывает, как проверить:

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

А вот пример вывода :

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! 

Теперь это не касается первоначальной проблемы, которая подразумевает отрицательные числа. Чтобы решить этот случай, выделите все отрицательные числа и вычислите все комбинации отрицательных чисел, с суммой.

Тогда для каждой суммы отрицательного числа, создать вложенную задачу, содержащую только положительные числа и соответствующую цель (начальная цель - сумма отрицательных чисел)

Один из способов улучшить его: Сложность задач зависит по числу комбинаций отрицательных чисел. Таким образом, если число отрицательных чисел больше, чем положительное, вы можете просто инвертировать все значения и решить проблему инверсии.

Еще один способ улучшить его: вы можете сохранить в памяти сумму положительных чисел каждой проблемы. Если сумма + nodeValue < целевая, то бесполезно продолжать исследовать ветку.