从一个总和等于零的集合中找到一个子集？

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

我在大学时代谷歌面试时就遇到了这个问题，并花了很长时间才解决它。

想一想，对于 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}