黑马程序员技术交流社区

标题: 在n个整数中找到相加之和为t的所有组合 [打印本页]

作者: 郭孟涛    时间: 2013-1-29 00:20
标题: 在n个整数中找到相加之和为t的所有组合
本帖最后由 郭孟涛 于 2013-2-3 13:12 编辑

给定一个数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:}


作者: 梁永奇    时间: 2013-1-29 00:20
本帖最后由 梁永奇 于 2013-1-30 04:00 编辑

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

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


作者: 许晓华    时间: 2013-1-29 08:19
集合里为什么有重复的数,是否要先去重?
作者: vmvm555    时间: 2013-1-29 22:46
我想了两个钟头没想出来,写了一段代码,但是好像得到的结果不完整,不好意思发上来
作者: 杨玲    时间: 2013-1-29 22:51
vmvm555 发表于 2013-1-29 22:46
我想了两个钟头没想出来,写了一段代码,但是好像得到的结果不完整,不好意思发上来 ...

呵呵 ,我也差不多!难点就在于它有可能是3个或者4个..N个数相加等于这个数T,我打算用集合试试!
作者: 郭孟涛    时间: 2013-1-29 23:27
vmvm555 发表于 2013-1-29 22:46
我想了两个钟头没想出来,写了一段代码,但是好像得到的结果不完整,不好意思发上来 ...

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

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

有时候,我觉得写代码既是数学运算,又更加像是语文作文。能把一个意思用一篇文章形容出来,还是用一首诗形容出来,还是需要不段的锤炼。
作者: 郭孟涛    时间: 2013-1-30 00:39
许晓华 发表于 2013-1-29 08:19
集合里为什么有重复的数,是否要先去重?

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

比如其中 3加上第一个1等于四,加上第二个1也等于四,只需要输出 一个 3+1 即可。
作者: 梁永奇    时间: 2013-1-30 03:49
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 13:51
梁永奇 发表于 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 16:27
郭孟涛 发表于 2013-1-30 13:51
两个编译都可以通过,运行是都提示错误:

我的代码是用myeclipse写的,刚才打开editplus,把我给你的代码复制进去,测试了一下,一点问题没有,成功输出结果。你是不是类名什么的写错了?系统提示"java.lang.NoClassDefFoundError: HelloWorld "
作者: 郭孟涛    时间: 2013-1-30 19:45
梁永奇 发表于 2013-1-30 16:27
我的代码是用myeclipse写的,刚才打开editplus,把我给你的代码复制进去,测试了一下,一点问题没有,成 ...

我去掉package cn.itcast;的时候,运行会出现结果。可能和头部这个package cn.itcast;有关吧。
作者: 姚永生    时间: 2013-2-2 15:55
/**
花了好几天的时间,终于把它做出来了。
还是楼上的梁咏琪哥们厉害,在最短的时间内用最简便的方法做出来
我这个程序没有使用递归,因为,对递归还是不太懂。
做的不是很理想,打了两个大补丁,但是总算是做出来了,一个字,爽。
老毕同志教导我们说:我顶,我顶,顶顶顶顶顶顶!!
最后感谢楼主贡献的题目。
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
考虑负数吗?
作者: 郭孟涛    时间: 2013-2-2 20:23
朱玉玺 发表于 2013-2-2 20:18
考虑负数吗?

应该是包括负数,我觉得int类型的就可以吧
作者: 朱玉玺    时间: 2013-2-3 10:35
本帖最后由 朱玉玺 于 2013-2-3 10:40 编辑

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

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


作者: 朱玉玺    时间: 2013-2-3 11:30
刚才看了一个帖子http://bbs.itheima.com/forum.php ... mp;extra=#pid223937回复中有个哥们说这个帖子算法的核心是求出N个数中选出M个的排列问题,我觉得你这个帖子的核心问题也是这个。




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2