一道java题目，大家来设计一下，看看谁的最简单！

Question

任意给一数组，如{-10，45，35，99，10，6，9，20，17，18}
再任意给一个值，如35.
请从上面的数组中找出所有的组合，使他们的和等于35.
例如对于上面的数组，所有的组合情况为：
35；
-10+45；
17+18；
6+9+20；
-10+35+10；
-10+17+18+10；
-10+6+9+20+10；
注意，每一种组合中一个数只能出现一次。

Answer 1

先来个正常思路的【这个挺繁琐，再研究其它思路】public class Test2 {    private static int sum = 35;    private static int[] intArrays = { -10, 45, 35, 99, 10, 6, 9, 20, 17, 18 };    private static List<int[]> getResult(int[] intArrays, int sum) {        List<int[]> valueList = new ArrayList<int[]>();
        int[] value = null;        for (int i1 = 0; i1 < intArrays.length; i1++) {
            if (intArrays[i1] == sum) {
                value = new int[] { intArrays[i1] };
                valueList.add(value);
            }
            for (int i2 = i1 + 1; i2 < intArrays.length; i2++) {
                if (intArrays[i1] + intArrays[i2] == sum) {
                    value = new int[] { intArrays[i1], intArrays[i2] };
                    valueList.add(value);
                }
                for (int i3 = i2 + 1; i3 < intArrays.length; i3++) {
                    if (intArrays[i1] + intArrays[i2] + intArrays[i3] == sum) {
                        value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3] };
                        valueList.add(value);
                    }
                    for (int i4 = i3 + 1; i4 < intArrays.length; i4++) {
                        if (intArrays[i1] + intArrays[i2] + intArrays[i3] + intArrays[i4] == sum) {
                            value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3], intArrays[i4] };
                            valueList.add(value);
                        }
                        for (int i5 = i4 + 1; i5 < intArrays.length; i5++) {
                            if (intArrays[i1] + intArrays[i2] + intArrays[i3] + intArrays[i4] + intArrays[i5] == sum) {
                                value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3], intArrays[i4],
                                        intArrays[i5] };
                                valueList.add(value);
                            }
                            for (int i6 = i5 + 1; i6 < intArrays.length; i6++) {
                                if (intArrays[i1] + intArrays[i2] + intArrays[i3] + intArrays[i4] + intArrays[i5]
                                        + intArrays[i6] == sum) {
                                    value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3], intArrays[i4],
                                            intArrays[i5], intArrays[i6] };
                                    valueList.add(value);
                                }
                                for (int i7 = i6 + 1; i7 < intArrays.length; i7++) {
                                    if (intArrays[i1] + intArrays[i2] + intArrays[i3] + intArrays[i4] + intArrays[i5]
                                            + intArrays[i6] + intArrays[i7] == sum) {
                                        value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3], intArrays[i4],
                                                intArrays[i5], intArrays[i6], intArrays[i7] };
                                        valueList.add(value);
                                    }
                                    for (int i8 = i7 + 1; i8 < intArrays.length; i8++) {
                                        if (intArrays[i1] + intArrays[i2] + intArrays[i3] + intArrays[i4]
                                                + intArrays[i5] + intArrays[i6] + intArrays[i7] + intArrays[i8] == sum) {
                                            value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3],
                                                    intArrays[i4], intArrays[i5], intArrays[i6], intArrays[i7],
                                                    intArrays[i8] };
                                            valueList.add(value);
                                        }
                                        for (int i9 = i8 + 1; i9 < intArrays.length; i9++) {
                                            if (intArrays[i1] + intArrays[i2] + intArrays[i3] + intArrays[i4]
                                                    + intArrays[i5] + intArrays[i6] + intArrays[i7] + intArrays[i8]
                                                    + intArrays[i9] == sum) {
                                                value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3],
                                                        intArrays[i4], intArrays[i5], intArrays[i6], intArrays[i7],
                                                        intArrays[i8], intArrays[i9] };
                                                valueList.add(value);
                                            }
                                            for (int i10 = i9 + 1; i10 < intArrays.length; i10++) {
                                                if (intArrays[i1] + intArrays[i2] + intArrays[i3] + intArrays[i4]
                                                        + intArrays[i5] + intArrays[i6] + intArrays[i7] + intArrays[i8]
                                                        + intArrays[i9] + intArrays[i10] == sum) {
                                                    value = new int[] { intArrays[i1], intArrays[i2], intArrays[i3],
                                                            intArrays[i4], intArrays[i5], intArrays[i6], intArrays[i7],
                                                            intArrays[i8], intArrays[i9], intArrays[i10] };
                                                    valueList.add(value);
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }        return valueList;
    }    public static void main(String[] args) {        List<int[]> valueList = getResult(intArrays, sum);
        for (int[] value : valueList) {
            for (int i : value) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

Answer 2

典型的背包算法～
http://topic.csdn.net/t/20041209/17/3631007.html
自己参考下吧

Answer 3

写一下思路：
    假设，m为要找的和，也即题中的35
   1、按顺序取出数组中的值,设为a[i]，如果取的值大于m，程序中止
   2、令m=m-a[i]
   3、如果m=0，则找到了一组符合要求的数；否则继续第一步；

Answer 4

    private static int[] bags = { -10, 45, 35, 99, 10, 6, 9, 20, 17, 18};   
    public static int total(int index, int sum) {
        if (index > bags.length - 1) {
            return 0;
        }
        if(sum >= bags[index]) {
            int result = total(index + 1, sum - bags[index]);
            if (result == sum - bags[index]) {
                System.out.print(bags[index] + " ");
                return sum;
            }
        }
        return total(index + 1, sum);
    }    public static void main(String args[]) {
     for(int i = 0 ; i < bags.length ; i ++){
     total(i, 35);
     }
    }

Answer 5

在以上思路上想的,抛砖引玉之用,希望有高手给出思路及程序哦.1、按顺序取出数组中的值，设为a[i]。
2、令m=m-a[i].
3、将m与数组中的所有值作一次比较，如果相等，则找到一组值。并重新返回1步for循环。

Answer 6

本帖最后由 AWUSOFT 于 2009-03-05 13:23:38 编辑

  

Answer 7

private static int[] bags = { -10, 45, 35, 99, 10, 6, 9, 20, 17, 18};   
    public static int total(int index, int sum) {
        if (index > bags.length - 1) {
            return 0;
        }
        if(sum >= bags[index]) {
            int result = total(index + 1, sum - bags[index]);
            if (result == sum - bags[index]) {
                System.out.print(bags[index] + " ");
                return sum;
            }
        }
        return total(index + 1, sum);
    }    public static void main(String args[]) {
        for(int i = 0 ; i < bags.length ; i ++){
            total(i, 35);
        }
    }

Answer 8

典型的0-1背包问题。最坏情况下的时间复杂度是2^n,用动态规划算法的时间复杂度是n*m。其中n是数组的长度
，m是目标和（就是本题中的35）。

Answer 9

........牛人家族啊！期待ing~~~~~~~~~

Answer 10

这种组合求全解的话,本来就没什么特别高效的算法,因为解的数量就很大,数稍微多一些的话!上百万个解不稀奇!如果只是求1个解,那就简单多了!先对原数组排序,做个累加统计,然后再用递归搜索,配上hash,
就不用每次都递归到最后1步,配合累加进行剪枝,效率还过的去!

Answer 11

楼主，请问你这个： private static int sum = 35;    private static int[] intArrays = { -10, 45, 35, 99, 10, 6, 9, 20, 17, 18 };中是给定的一个数组，加入要随即的输入一个一维数组的话，那么这个题目该怎么样才能解呢？

Answer 12

思路：
1）数组按大小排序，得sortArr[]
2）标出sortArr中负数和正数的分界下标X
3）标出比给定值（35）大的下标Y
之后再。不过这个可能不是最简单，而是性能好

Answer 13

看看吧，大致思路就是排列组合，然后求和的方法，这个是考虑到顺序的问题的，如果不考虑顺序，需要排列组合上修改一下，这个是我随便写的，效率没有考虑，但是应该可以满足算出的条件public class TestDemo { public static int ct =35;
public static void main(String args[]){ String[] s = {"-10","45","35","99","10","6","9","20","17","18"};
//String[] s = {"1","2","3","4","5","6","7"};
ArrayList list = new ArrayList(s.length);
for(int i=0;i<s.length;i++){
list.add(s[i]);
}

ArrayList list2 = null;
ArrayList list3 = null;
for(int j=1;j<=s.length;j++){
for (int i=0;i<s.length;i++){
list2=(ArrayList)list.clone();
list3 = new ArrayList();
String data = (String)list2.remove(i);
list3.add(data);
     getPos(list3,list,data,j,1);
}
}
}


private static void getPos(ArrayList hasArray,ArrayList newArray,String title,int pos,int num){
if(pos==1){
if(title.equals("35")){
System.out.println(title);
}
}else{
num=num+1;
if(num==pos){
for(int i=0;i<newArray.size();i++){
if(!hasArray.contains(newArray.get(i))){
if(isOut(title+"+"+newArray.get(i)))
System.out.println(title+"+"+newArray.get(i));
}
}
} for(int i=0;i<newArray.size();i++){
if(!hasArray.contains(newArray.get(i))){
ArrayList tArray = (ArrayList)hasArray.clone();
tArray.add(newArray.get(i));
String title2 = title+"+"+newArray.get(i);
getPos(tArray,newArray,title2,pos,num);
}
}
  }
}

private static boolean  isOut(String s){
String[] ss = s.split("\\+");
int result = 0;
for(int i=0;i<ss.length;i++){
result = result+Integer.parseInt(ss[i]);
}
if(result==ct){
return true;
}else{
return false;
}
}
}

Answer 14

首先说一下我的思路，只适合数组中全是正数的情况，待会儿给出代码：
1、对数组a[n]按降序排序。
2、i=0；
3、若i>=a.lenth,转10。
4、j=i；
5、若j>=a.lenth，转9。
6、a[j]入栈，j++。
7、若栈中所有数的和小于目标数，转5。
8、若栈中所有数的和大于目标数，j--,栈顶出栈，转5。
9、（注意此时内层循环结束循环）若栈中所有数的和等于目标数，则打印栈中的所有数，清空栈，i++,转3。
10、结束。

Answer 15

直接由1-1024产生各种组合计算似乎更直接,我也写了个...
public class Test {
private static int[]arr={-10,45,35,99,10,6,9,20,17,18};
public static void main(String[] args) {
for(int i=1;i<Math.pow(2, arr.length);i++){
int sum=0, temp=i, index=0;
while(temp>0){
if(temp%2==1)sum+=arr[index];
temp>>=1;
index++;
}
if(sum==35) print(i);
}
}
//输出结果
public static void print(int i){
int index=0;
while(i>0){
if(i%2==1){
System.out.print(arr[index]);
System.out.print(' ');
}
i>>=1;
index++;
}
System.out.println(' ');
}
}

Answer 16

public class NotSay
{
   public static void main(String[] args){
      int[] original={99,45,35,20,18,17,10,9,6};//初始数组
      int target=35; //目标和
      int[] stack=new int[original.length];
      for(int a:stack) //初始化栈
       a=0;
      
      for(int i=flag;i<original.length;i++){
       int stackTop=0;
       int stackSum=0;
              
       for(int j=i;j<original.length;j++){
       
       stack[stackTop]=original[j];
       stackSum+=stack[stackTop]; //求栈中数的和
       stackTop++;
       if(stackSum>target){ //若栈中的数的和大于目标数，则栈顶出栈
       stackTop--;
       stackSum=stackSum-stack[stackTop];
       stack[stackTop]=0; 
       }       
       }
       
       if(stackSum==target){  //内层循环结束后，判断栈中存放的数的和指定是小于或等于目标数的，若栈中数的和等于目标数则打印
       for(int t=0;t<stackTop;t++)
       System.out.print(stack[t]+" ");
       
       System.out.println();
       }
      
      }
      
   }
}这个代码是根据我在67楼的算法写出来的。这个只能处理数组中全是正数的情况，望高手指点加入负数该做何修改。
还有一个小bug就是，该程序会重复打印35三次。时间紧迫，没空修复。

Answer 17

对不起，我的上面的小程序有个错误，重发一次：public class NotSay
{
   public static void main(String[] args){
      int[] original={-10,99,45,35,20,18,17,10,9,6};//初始数组
      int target=35; //目标和
      int[] stack=new int[original.length];
      for(int a:stack) //初始化栈
       a=0;
      
      for(int i=0;i<original.length;i++){
       int stackTop=0;
       int stackSum=0;
              
       for(int j=i;j<original.length;j++){
       
       stack[stackTop]=original[j];
       stackSum+=stack[stackTop]; //求栈中数的和
       stackTop++;
       if(stackSum>target){ //若栈中的数的和大于目标数，则栈顶出栈
       stackTop--;
       stackSum=stackSum-stack[stackTop];
       stack[stackTop]=0; 
       }       
       }
       
       if(stackSum==target){  //内层循环结束后，判断栈中存放的数的和指定是小于或等于目标数的，若栈中数的和等于目标数则打印
       for(int t=0;t<stackTop;t++)
       System.out.print(stack[t]+" ");
       
       System.out.println();
       }
      
      }
      
   }
}
刚才测试了一下，这个程序可以处理有负数的情况。望高手修复一下重复打印35的bug。

Answer 18

这是个动态规划的题目 具体做法thinking

Answer 19

哇哈哈哈，这个程序真是
太
壮观啦
我第一次看到如此规模的for循环嵌套
如果真要这么写的话应该是一个递归吧？？
没有仔细想过，随便说说

Answer 20

其实这个题不难的：写个大概过程
int[] a ;
for(int i=0; i<a.length;i++){
   for(int j=i+1;j<a.length;j++){
     if(a[i]+a[j] ==35){
        System.out.println("a[i]+a[j]="+"a["+i+"]+a["+j+"]");
     }
   }
}
这样应该是可以算出来的吧

Answer 21

简单的思路就是穷举了n=数组长；
static combonumber=0;
static int[] arr=new int[n]；
dictionary<int,int[]> comboindex=new dictionary<int,int[]>();
void combo(int n,int m,int k,int count)
{
if(count==m)
{
int[]temp=new int[m];
Array.copy(arr,0,temp,0,m);
comboindex.add(combonumber++,temp);
return;
}
for(int i=k;i<n;i++)
{
  arr[count]=i;
  combo(n,m,i+1,count+1);
}
for(int i=1;i<=n;i++)
{
 combo(n,i,0,0);
}
int sum=0;
for(int i=0;i<combonumber;i++)
{
 foreach(int t in comboindex[i])
   sum+=t;
 if(sum==35)
  {
   输出；
   }
 }
}

Answer 22

public class DiYizhang {
public int suanfa(int number)
{
int jie=0;
int count=0
int num[]=new int []{-10,45,35,99,10,6,9,20,17,18};
for(int i=0;i<num.length;i++)
{
for(int j=0;j<num.length-i;j++)
{
     for(int k=0;k<=j;k++)
     {
      count+=num[k];
      if(count==number)
      {
          jie++;
      }
     }
}
}
return jie;
} public static void main(String[] args) {
DiYizhang di = new DiYizhang();
System.out.print(di.suanfa(35));
}
}
我不知道这样对不对，只能算出有几种的组合。至于把组合情况吗？没有想到，7楼的兄弟太牛B了

Answer 23

public class DiYizhang {
public int suanfa( int number)
{
int jie=0;
int num[]=new int []{-10,45,35,99,10,6,9,20,17,18};
for(int i=0;i<num.length;i++)
{
for(int j=0;j<num.length-i;j++)
{
int count=0;
     for(int k=0;k<=j;k++)
     {
      count+=num[k];
     }
     if(count==number)
      {
          jie++;
      }
}
}
return jie;
} public static void main(String[] args) {
DiYizhang di = new DiYizhang();
System.out.print(di.suanfa(35));
}
}
楼主，是不是9次，

Answer 24

ACM题目，可用动态规划解，类似0-1背包问题...呵呵

Answer 25

  先把数组分为保存三个数组集合 
   A{x>35} B{0<x<35}  C{x<0}
然后 B内部两个数相关，如果能有等于35的记录下来
A与C中的数相加有等于35的记录下来