从一个总和等于零的集合中找到一个子集？ [英] to find a subset from a set whose sum equals to zero?
问题描述
我有一组这样的整数
{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; （b i = 0; i< numbers.size（）; i ++）
ArrayList<整数> 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）;
}
}
这里是一个解决方案。
我首先解决第一个子问题：我认为所有数字和目标都是正数然后我解决了真正的问题。 / p>
为了达到这个目的，我基本上解决了子问题中的问题。
让我们用一个例子说明：
数字：1,3,8,2,7目标：10
首先：排序清单：
数字：8,7,3,2,1目标：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;
公共类问题{
/ *
*最后用于重构解决方案。
*对于根问题，此值为null。
* /
private Integer nodeValue;
// POSITIVE目标总和
private int target;
//应该排序的正数的列表
private List< Integer>数;
private List<问题> listSubProblems;
/ *
*链接到父问题。
*最后用于生成结果。
* /
private问题parentProblem;
public问题（int target，List< Integer> number，Integer nodeValue，Problem parentProblem）{
this.target = target;
this.numbers =数字;
this.nodeValue = nodeValue;
this.parentProblem = parentProblem;
this.listSubProblems = new ArrayList< Problem>（）;
}
public void solve（）{
buildSubProblems（）;
for（问题：listSubProblems）{
problem.solve（）;
}
}
/ **
*构建子问题列表。
*例如，如果{@link #numbers}包含9 8 5 3，目标10
*此方法将返回以下子问题：
*
*<表>
*< tr>
*< td> nodeValue< / td>< td> target< / td>< td>数字< / 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（）;
/ *
*数字应为正数，因此如果目标是负数，
*则没有机会找到有效的解决方案。
*当数字列表被排序时，目标< 0快速发生
*因此，如果（目标> = 0&& numbersSize> 1）{
}，它会快速删除隐含大数字
* /
的组合for（int i = 0; i< numbersSize; i ++）{
Integer nodeValue = numbers.get（i）;
列表<整数>子列表= numbers.subList（I + 1，numbersSize）;
int newTarget = this.target-nodeValue;
问题问题=新问题（newTarget，subList，nodeValue，this）;
System.out.println（Created problem：+ problem.dump（））;
this.listSubProblems.add（问题）;
}
}
}
/ **
* @return True是问题只包含一个数字，且该数字等于目标。
* /
public boolean isNodeSolution（）{
return this.target == 0;
}
public Integer getNodeValue（）{
return this.nodeValue;
}
公开列表<问题> getListSubProblems（）{
返回this.listSubProblems;
}
public问题getParentProblem（）{
返回this.parentProblem;
}
public String dump（）{
StringBuilder sb = new StringBuilder（）;
sb.append（{nodeValue：+ this.nodeValue）;
sb.append（; target：+ target）;
sb.append（; numbers：）;
for（整数整数：数字）{
sb.append（integer +，）;
}
sb.append（}）;
sb.append（有效？：+ isNodeSolution（））;
返回sb.toString（）;
}
}
这是代码，显示如何测试它：
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
公共类Main {
public static void main（String [] args）throws Exception {
整数number [] = {1,3,8,2 ，7};
int target = 10;
列表<整数> listNumbers = Arrays.asList（numbers）;
Collections.sort（listNumbers）;
Collections.reverse（listNumbers）;
//构建根问题
问题问题=新问题（target，listNumbers，null，null）;
//解决它
problem.solve（）;
//转储结果。
dumpResult（问题）;
System.out.println（完成！）;
}
private static void dumpResult（问题）{
for（问题p：problem.getListSubProblems（））{
if（p.isNodeSolution（）） {
System.out.print（\ nSolution：）;
dumpSolution（p）;
}
dumpResult（p）;
}
}
private static void dumpSolution（问题）{
//如果当前节点不是根问题
if（问题。 getParentProblem（）！= null）{
System.out.print（problem.getNodeValue（）+，）;
dumpSolution（problem.getParentProblem（））;
}
}
}
这是一个例子输出：
创建问题：{nodeValue：8;目标：2;数字：7,3,2,1，}有效？ ：false
创建的问题：{nodeValue：7;目标：3;数字：3,2,1，}有效？ ：false
创建问题：{nodeValue：3;目标：7;数字：2,1，}有效？ ：false
创建问题：{nodeValue：2;目标：8;编号：1，}有效？ ：false
创建的问题：{nodeValue：1;目标：9;数字：}有效？ ：false
创建的问题：{nodeValue：7;目标：-5;数字：3,2,1，}有效？ ：false
创建问题：{nodeValue：3;目标：-1;数字：2,1，}有效？ ：false
创建问题：{nodeValue：2;目标：0;编号：1，}有效？ ：true
创建问题：{nodeValue：1;目标：1;数字：}有效？ ：false
创建问题：{nodeValue：3;目标：0;数字：2,1，}有效？ ：true
创建问题：{nodeValue：2;目标：1;编号：1，}有效？ ：false
创建的问题：{nodeValue：1;目标：2;数字：}有效？ ：false
创建问题：{nodeValue：2;目标：-2;编号：1，}有效？ ：false
创建的问题：{nodeValue：1;目标：-1;数字：}有效？ ：false
创建问题：{nodeValue：2;目标：5;编号：1，}有效？ ：false
创建的问题：{nodeValue：1;目标：6;数字：}有效？ ：false
解决方案：2,8，
解决方案：3,7，完成！
现在，这并未涵盖隐含负数的初始问题。
要解决这种情况，请隔离所有负数并计算负数的所有组合，其中总和。
然后，对于每个负数的总和，创建一个只包含正数和相应目标的子问题（初始目标 - 负数之和）
改善它的一种方法：问题的复杂性取决于数量负数组合。因此，如果负数多于正数，则可以反转所有值并解决反转问题。
另一种改进它的方法：你可以在内存中维护每个子问题的正数之和。如果sum + nodeValue<目标是继续探索分支是没用的。
I have a set of integers like this
{1,4,5,2,7,8,-3,-5,-6,9,3,-7,-1,5,6}
the set can contain any number of items as input is taken from the user I need to find all possible subsets from this set whose sum equals to zero for example in this case in the above set the subsets will be
{(1,2,-3)}
{(1,-1)}
{(3,-3)}
{(5,-5)}
etc etc
I have tried this code but it is not returning me answer when I am setting target equal to 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);
}
}
Here is a proposition of solution.
I first solve a first sub-problem : I suppose that all the numbers and the target are positive number then I solve the real problem.
To achieve this, I basically decompose the problem in sub-problems.
Let's illustrate with an example :
Numbers : 1,3,8,2,7 target :10
First : sort the list: Numbers : 8,7,3,2,1 target :10 Then find recursively the solutions to the following problems :
Numbers : 7,3,2,1 target :10-8 = 2
Numbers : 3,2,1 target :10-7=3
Numbers : 2,1 target : 10-3=2
Numbers : 1 target : 10-1=9
The aim of placing big numbers before is to quickly eliminate solutions including this number (because the sum quickly exceeds the target).
Here is the commented code for the resolution of this sub-problem:
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();
}
}
Here is the code which shows how to test it:
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());
}
}
}
And here is an example of output:
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!
Now, this does not cover the initial problem which implies negative numbers. To solve this case, isolate all negative numbers and compute all combinations of negative numbers, with there sum.
Then, for each sum of negative number, create a sub problem containing only positive numbers and a corresponding target (initial target - sum of negative numbers)
One way to improve it: The complexity of the problems depends on the number of combinations of negative numbers. So, if there are more negative numbers than positive numbers, you can just invert all values and solve the invert problem.
Another way to improve it: You can maintain in memory the sum of positive numbers of each sub-problems. If sum + nodeValue < target then it is useless to continue exploring the branch.
这篇关于从一个总和等于零的集合中找到一个子集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
