给定一个数t，以及n个整数，在这n个整数中找到相加之和为t的所有组合，例如t = 4，n = 6，这6个数为[4, 3, 2, 2, 1, 1]，这样输出就有4个不同的组合，它们的相加之和为4：4, 3+1, 2+2, and 2+1+1。请设计一个高效算法实现这个需求



我个人分析：
   发现这个题目的大难点，不仅仅任意两个数的和等于给定的数，还要计算任意三个甚至多个数的组合，比如示例中的 2+1+1的三个数的组合也等于4 。
我的一个思路：
  1.如果其中一个数，小于给定数。分析其跟另外每个数的的和是否等于给定数。等于的时候输出，小于的时候再往下分析
  2.如果其中二个数，小于给定数。分析其跟另外每个数的的和是否等于给定数。等于的时候输出，小于的时候再往下分析
  3.如果其中三个数，小于给定数。分析其跟另外每个数的的和是否等于给定数。等于的时候输出，小于的时候再往下分析
  4.如果其中四个数，小于给定数。分析其跟另外每个数的的和是否等于给定数。等于的时候输出，小于的时候再往下分析
  .
  .
  .
  .
  一直到所有数的总个数

按照我这个思路，我还没想处怎么嵌套这些循环。{:soso_e115:}

我把代码简化了，所以上面的代码看起来比较费劲，我把最初写的代码给你复制过来吧。你题目中的意思，应该是不需要去重的

package cn.itcast;


public class HelloWorld
{
        public static void main(String args[])
        {               
                int[] shuzu = {2,6,9,4,0,1,8,2,7,2,2,4,2,1,1,1,1};//这是你题目中的n个整数，我放在了数组中
                int jieguo = 8;//这是你题目中的t
                qiuHe(shuzu,jieguo);
        }
        public static void  qiuHe(int[] shuzu,int jieguo)
        {
                int len = shuzu.length;
                for(int m=0;m<len-1;m++)
                {
                        for(int n=m+1;n<len;n++)
                        {
                                if((shuzu[m]+shuzu[n])==jieguo)
                                {
                                        System.out.println("组合:"+shuzu[m]+"+"+shuzu[n]);
                                }
                                else if((shuzu[m]+shuzu[n])<jieguo)
                                {
                                        int he = shuzu[m]+shuzu[n];
                                        int[] arr = {shuzu[m],shuzu[n]};
                                        qiuHe2(shuzu,n,he,jieguo,arr);
                                }
                        }
                }
                for(int x=0;x<len;x++)
                {
                        if(shuzu[x]==jieguo)
                        {
                                System.out.println("组合:"+jieguo);
                        }
                }
        }
        public static void qiuHe2(int[] shuzu,int kaishiweizhi,int he,int jieguo,int[] xinshuzu)//这个函数用来求出组合
        {
                for(int position=kaishiweizhi+1;position<shuzu.length;position++)
                {
                        if((he+shuzu[position])==jieguo)
                        {
                                System.out.print("组合：");
                                for(int x=0;x<xinshuzu.length;x++)
                                {
                                        System.out.print(xinshuzu[x]+"+");
                                }
                                System.out.println(shuzu[position]);
                        }
                        else if((he+shuzu[position])<jieguo)
                        {
                                int temp = xinshuzu.length+1;
                                int[] newarry = new int[temp];
                                for(int lennewarry=0;lennewarry<temp-1;lennewarry++)
                                {
                                        newarry[lennewarry] = xinshuzu[lennewarry];
                                }
                                newarry[temp-1] = shuzu[position];
                                int he1 = he+shuzu[position];
                                qiuHe2(shuzu,position,he1,jieguo,newarry);
                        }
                }
        }
}

集合里为什么有重复的数，是否要先去重？

我想了两个钟头没想出来，写了一段代码，但是好像得到的结果不完整，不好意思发上来

vmvm555 发表于 2013-1-29 22:46
我想了两个钟头没想出来，写了一段代码，但是好像得到的结果不完整，不好意思发上来 ...

呵呵 ,我也差不多!难点就在于它有可能是3个或者4个..N个数相加等于这个数T,我打算用集合试试!

vmvm555 发表于 2013-1-29 22:46
我想了两个钟头没想出来，写了一段代码，但是好像得到的结果不完整，不好意思发上来 ...

呵呵，我也是，昨天我是想用冒泡排序求一个数组的最大方法哪个思路求来。结果弄了两个钟头，觉得代码结构有点乱，不够清晰。也没好意思发。

今天我想了一下，不能一味的追求简练，即使多加几个变量先实现了功能。再逐步精简。如果碰到考核的时候的不至于太难看。

有时候，我觉得写代码既是数学运算，又更加像是语文作文。能把一个意思用一篇文章形容出来，还是用一首诗形容出来，还是需要不段的锤炼。

许晓华 发表于 2013-1-29 08:19
集合里为什么有重复的数，是否要先去重？

根据题目中给出的示例显示，需要去重。

比如其中 3加上第一个1等于四，加上第二个1也等于四，只需要输出 一个 3+1 即可。

package cn.itcast;


public class HelloWorld
{
        public static void main(String args[])
        {               
                int[] shuzu = {2,6,9,4,0,1,8,2,7,2,2,4,2,1,1,1,1};//这是你题目中的n个整数，我放在了数组中
                int jieguo = 8;//这是你题目中的t
                int[] arr = {};
                qiuHe(shuzu,0,0,jieguo,arr);
        }
        public static void qiuHe(int[] shuzu,int kaishiweizhi,int he,int jieguo,int[] xinshuzu)//这个函数用来求出组合
        {
                for(int position=kaishiweizhi+1;position<shuzu.length;position++)
                {
                        if((he+shuzu[position])==jieguo)
                        {
                                System.out.print("组合：");
                                for(int x=0;x<xinshuzu.length;x++)
                                {
                                        System.out.print(xinshuzu[x]+"+");
                                }
                                System.out.println(shuzu[position]);
                        }
                        else if((he+shuzu[position])<jieguo)
                        {
                                int temp = xinshuzu.length+1;
                                int[] newarry = new int[temp];
                                for(int lennewarry=0;lennewarry<temp-1;lennewarry++)
                                {
                                        newarry[lennewarry] = xinshuzu[lennewarry];
                                }
                                newarry[temp-1] = shuzu[position];
                                int he1 = he+shuzu[position];
                                qiuHe(shuzu,position,he1,jieguo,newarry);
                        }
                }
        }
}
我做过测试，没问题的，:-)

梁永奇 发表于 2013-1-30 03:57
我把代码简化了，所以上面的代码看起来比较费劲，我把最初写的代码给你复制过来吧。你题目中的意思，应该是 ...

两个编译都可以通过，运行是都提示错误：

1. ---------- JAVA ----------
   
2. java.lang.NoClassDefFoundError: HelloWorld (wrong name: cn/itcast/HelloWorld)
   
3.         at java.lang.ClassLoader.defineClass1(Native Method)
   
4.         at java.lang.ClassLoader.defineClass(ClassLoader.java:791)
   
5.         at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:142)
   
6.         at java.net.URLClassLoader.defineClass(URLClassLoader.java:449)
   
7.         at java.net.URLClassLoader.access$100(URLClassLoader.java:71)
   
8.         at java.net.URLClassLoader$1.run(URLClassLoader.java:361)
   
9.         at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
   
10.         at java.security.AccessController.doPrivileged(Native Method)
    
11.         at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
    
12.         at java.lang.ClassLoader.loadClass(ClassLoader.java:423)
    
13.         at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
    
14.         at java.lang.ClassLoader.loadClass(ClassLoader.java:356)
    
15.         at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:482)
    
16. Exception in thread "main"
    
17. 输出完成 (耗时 0 秒) - 正常终止

复制代码

郭孟涛 发表于 2013-1-30 13:51
两个编译都可以通过，运行是都提示错误：

我的代码是用myeclipse写的，刚才打开editplus，把我给你的代码复制进去，测试了一下，一点问题没有，成功输出结果。你是不是类名什么的写错了？系统提示"java.lang.NoClassDefFoundError: HelloWorld "

梁永奇 发表于 2013-1-30 16:27
我的代码是用myeclipse写的，刚才打开editplus，把我给你的代码复制进去，测试了一下，一点问题没有，成 ...

我去掉package cn.itcast;的时候，运行会出现结果。可能和头部这个package cn.itcast;有关吧。

/**
花了好几天的时间，终于把它做出来了。
还是楼上的梁咏琪哥们厉害，在最短的时间内用最简便的方法做出来
我这个程序没有使用递归，因为，对递归还是不太懂。
做的不是很理想，打了两个大补丁，但是总算是做出来了，一个字，爽。
老毕同志教导我们说：我顶，我顶，顶顶顶顶顶顶！！
最后感谢楼主贡献的题目。
Happy new year!!
*/

class  TestSum12
{
        public static void main(String[] args)
        {
                int[]arr = new int[]{2,6,9,4,0,1,8,2,7,2,2,4,2,1,1,1,1,-1};//给定数组
                int t = 8;//条件。

                //如果符合条件打印单个元素
                int sum = 0;
                for (int i=0; i<arr.length; i++)
                {
                        if(arr[i]==t)
                                System.out.println(arr[i]+"["+i+"]"+" = "+t);
                        sum = sum+arr[i];
                }
                //如果符合条件，打印全部元素的组合
                if(sum==t)
                {
                        for (int i=0; i<arr.length-1; i++)
                        {
                                System.out.print(arr[i]+"["+i+"]"+" +");
                        }
                        System.out.println(arr[arr.length-1]+"["+(arr.length-1)+"]"+" = "+t);
                }
                //打印其余的每一种相同的组合
                for (int i=2; i<arr.length; i++)
                {
                        compound(arr, i, t);//调用函数
                }
               

        }

        //这个方法用来打印符合条件的其他组合
        //这个方法不能打印从中取出一个元素的组合
        //也不能打印从中取出所有元素的组合，不知道差在哪里
                //欢迎大家给出意见
        //但是好在它现在貌似可以打印所有的其他组合，
        //我小试了一下，是可以的，按照我的思路也应该没有问题
        //我不想再思考了，太耗费时间。
        public static void compound(int []arr, int n, int t)
        {
                int sum = 0;
                int x[] = new int[n];//临时数组，用来存放并控制循环的指针

                //初始化数组
                for(int i=0; i<x.length-1; i++)
                {
                        x[i+1] = x[i]+1;
                }

                while (x[0]<arr.length-n)//最外层循环，用来使最末位不断自增。
                {
                        for (int i=0; i<x.length; i++)//第二层循环，用来判断是否产生进位
                        {
                                if(x[x.length-1-i]==arr.length-i)//判断后位是否产生进位
                                {
                                        x[x.length-2-i]++;//如果后位有进位，前位自增

                                        if(x[x.length-2-i]<=arr.length-2-i)
                                        {//如果前一位没有进位，给后位赋值
                                                x[x.length-1-i] = x[x.length-2-i]+1;
                                        }

                                        //判断后位与更多前位同时有进位时的操作
                                        else if (x[x.length-2-i]>arr.length-2-i)
                                        {//下面循环用来寻找适合的值，给最后位赋值
                                                for (int m=x.length-2-i; m>=0; m--)
                                                {
                                                        if(x[m]<arr.length-x.length+m)
                                                        {//根据找到的符合条件的数，给最后一位赋值
                                                                x[x.length-1-i] = x[m]+x.length-m-i;
                                                                m = -1;//找到恰当的数时，手动结束寻找循环。
                                                        }
                                                }
                                        }
                                }
                        }
                //判断是否符合条件
                for (int i=0; i<x.length; i++)
                {
                        sum = sum+arr[x[i]];
                }
                if(sum==t)
                {
                        //打印当前等式。
                        for(int i=0; i<x.length-1; i++)
                        {
                                System.out.print(arr[x[i]]+"["+x[i]+"]"+" + ");
                        }
                        System.out.println(arr[x[x.length-1]]+"["+x[x.length-1]+"] = "+t);
                }
                x[x.length-1]++;//最后位不断自增
                sum = 0;
                }
        }
}

考虑负数吗？

朱玉玺 发表于 2013-2-2 20:18
考虑负数吗？

应该是包括负数，我觉得int类型的就可以吧

题       目：
          给定一个数t，以及n个整数，在这n个整数中找到相加之和为t的所有组合， 例如t = 4，n = 6，这6个数为[4, 3, 2, 2, 1, 1]， 这样输出就有4个不同的组合，它们的相加之和为 4：4, 3+1, 2+2, and 2+1+1。 请设计一个高效算法实现这个需求
解题思路：
         1.判断这n个数之和是否为t，是在将其打印
         2.从n个数中取出一个数，判断剩余数之和是否为t，循环n次；
         3.每个循环内部又转到1，当求和元素只有两个时退出（求和最少得有2个元素）。
进一步分析：
         从上边得到打印出的结果，会出现重复，所以，将每次筛选出的组合存入TreeSet中，最后再打印TreeSet集合。
代码实现如下：

1. import java.util.ArrayList;
   
2. import java.util.Arrays;
   
3. import java.util.List;
   
4. import java.util.TreeSet;
   
5. 
   
6. public class NumberGroup {
   
7. //定义集合，存储组合。
   
8.         private static TreeSet<String> ts = new TreeSet<String>();
   
9.         public static void main(String[] args) {
   
10.                
    
11.                           Integer [] arr = {15,16,17,18,-1,-2,-3,0};                          
    
12.                           int key = 15;
    
13.                           //先对数组排序，以方便筛选，并使其打印结果有序。
    
14.                           Arrays.sort(arr);
    
15.                           //一开始用List的时候，filterNumGroup会报错，故转成ArrayList
    
16.                           List<Integer> list=Arrays.asList(arr);
    
17.                           ArrayList<Integer> nums=new ArrayList<Integer>(list);
    
18.                           //筛选组合
    
19.                           filterNumGroup(nums, key);                          
    
20.                           
    
21.                           //打印结果
    
22.                           for(String str:ts){
    
23.                                   System.out.println(str);
    
24.                           }                          
    
25.                         }
    
26.                         
    
27.                     public static void filterNumGroup(ArrayList<Integer> nums,int key){                    
    
28.                             if(key==getSum(nums)){        
    
29.                                     ts.add(getNumbers(nums));                                                        
    
30.                             }else{
    
31.                                     if(nums.size()>2){//此处如果2改为1，则会筛选出跟key（即t）相等的元素。
    
32.                                             //思路中的第2步。
    
33.                                             for(int index=0;index<nums.size();index++){
    
34.                                                     //此处，不能写成numsClone=nums，因为这样做它们指向的是同一个对象。
    
35.                                                     ArrayList<Integer> numsClone=new ArrayList<Integer>(nums);                                                   
    
36.                                                     numsClone.remove(index);//取出一个元素
    
37.                                                     filterNumGroup(numsClone,key);//递归调用
    
38.                                             }
    
39.                                     }
    
40.                             }
    
41.                     }
    
42.                     //求和
    
43.                     public static int getSum(List<Integer> nums){
    
44.                             int sum=0;        
    
45.                             for(Integer num:nums ){
    
46.                                     sum+=num;
    
47.                             }
    
48.                             return sum;
    
49.                         }
    
50.                     //将每一个组合转成String
    
51.                     public static String getNumbers(List<Integer> nums) {                        
    
52.                             StringBuilder sb = new StringBuilder();
    
53.                             for(Integer num:nums){
    
54.                                     sb.append(num+" ");
    
55.                             }                           
    
56.                             return sb.toString();                    
    
57.                                 
    
58.                         }
    
59. 
    
60.         
    
61. }
    

复制代码

小结：这个代码只能说是实现了功能，至于是否高效，我觉得还有优化的空间，这里就不做优化了。递归调用是有限制的，如果数字有成百上千个，那吃内存太厉害。
昨晚看到题，开始做，做完竟然停电了……悲剧~

刚才看了一个帖子http://bbs.itheima.com/forum.php ... mp;extra=#pid223937回复中有个哥们说这个帖子算法的核心是求出N个数中选出M个的排列问题，我觉得你这个帖子的核心问题也是这个。