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

我有一组像这样的整数

{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 numbers, int target, ArrayList  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 remaining = new ArrayList(); int n = numbers.get(i); for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j)); ArrayList partial_rec = new ArrayList(partial); partial_rec.add(n); sum_up_recursive(remaining,target,partial_rec); } } static void sum_up(ArrayList numbers, int target) { sum_up_recursive(numbers,target,new ArrayList()); } public static void main(String args[]) { Integer[] numbers = {3,4,6,4,5,2,6}; int target = 9; sum_up(new ArrayList(Arrays.asList(numbers)),target); } } 

Answer 1

这是一个解决方案的提议。

我首先解决第一个子问题：我认为所有数字和目标都是正数然后我解决了真正的问题。

为实现这一点，我基本上分解了子问题中的问题。

让我们用一个例子来说明：

数字：1,3,8,2,7目标：10

首先：对列表进行排序：数字：8,7,3,2,1 target：10然后递归查找以下问题的解决方案：

数字：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 numbers; private List listSubProblems; /* * Link to the parent problem. * Useful at the end to generate the results. */ private Problem parentProblem; public Problem(int target, List numbers, Integer nodeValue, Problem parentProblem){ this.target=target; this.numbers=numbers; this.nodeValue=nodeValue; this.parentProblem=parentProblem; this.listSubProblems =new ArrayList(); } 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: * *  *  *  *  *  * 8 5 3 *  *  * 5 3 *  *  * 3 *  * * 
nodeValue
target
numbers
9
10-9=1
8
10-8=2
5
10-5=5
 * */ 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 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 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 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! 

现在，这并不包括暗示负数的初始问题。 要解决这种情况，请隔离所有负数并计算负数的所有组合，其中总和。

然后，对于每个负数的和，创建一个只包含正数和相应目标的子问题（初始目标 – 负数之和）

改善它的一种方法：问题的复杂性取决于负数组合的数量。 因此，如果负数多于正数，则可以反转所有值并解决反转问题。

另一种改进方法：你可以在内存中保存每个子问题的正数之和。 如果sum + nodeValue

Answer 2

我在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 3

你没有检查partial是否为空，在这种情况下，当target == 0时， sum_up_recursive()会在第一次尝试时立即返回。试试这个：

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

请注意，可能还有其他方法可以大大改进您正在使用的算法。 我只是回答为什么你的代码没有按预期工作。