黑马程序员技术交流社区

标题: 在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
我把代码简化了，所以上面的代码看起来比较费劲，我把最初写的代码给你复制过来吧。你题目中的意思，应该是 ...

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

---------- JAVA ----------
java.lang.NoClassDefFoundError: HelloWorld (wrong name: cn/itcast/HelloWorld)
at java.lang.ClassLoader.defineClass1(Native Method)
at java.lang.ClassLoader.defineClass(ClassLoader.java:791)
at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:142)
at java.net.URLClassLoader.defineClass(URLClassLoader.java:449)
at java.net.URLClassLoader.access$100(URLClassLoader.java:71)
at java.net.URLClassLoader$1.run(URLClassLoader.java:361)
at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
at java.lang.ClassLoader.loadClass(ClassLoader.java:423)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
at java.lang.ClassLoader.loadClass(ClassLoader.java:356)
at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:482)
Exception in thread "main"
输出完成 (耗时 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 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集合。
代码实现如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;
public class NumberGroup {
//定义集合，存储组合。
private static TreeSet<String> ts = new TreeSet<String>();
public static void main(String[] args) {
Integer [] arr = {15,16,17,18,-1,-2,-3,0};
int key = 15;
//先对数组排序，以方便筛选，并使其打印结果有序。
Arrays.sort(arr);
//一开始用List的时候，filterNumGroup会报错，故转成ArrayList
List<Integer> list=Arrays.asList(arr);
ArrayList<Integer> nums=new ArrayList<Integer>(list);
//筛选组合
filterNumGroup(nums, key);
//打印结果
for(String str:ts){
System.out.println(str);
}
}
public static void filterNumGroup(ArrayList<Integer> nums,int key){
if(key==getSum(nums)){
ts.add(getNumbers(nums));
}else{
if(nums.size()>2){//此处如果2改为1，则会筛选出跟key（即t）相等的元素。
//思路中的第2步。
for(int index=0;index<nums.size();index++){
//此处，不能写成numsClone=nums，因为这样做它们指向的是同一个对象。
ArrayList<Integer> numsClone=new ArrayList<Integer>(nums);
numsClone.remove(index);//取出一个元素
filterNumGroup(numsClone,key);//递归调用
}
}
}
}
//求和
public static int getSum(List<Integer> nums){
int sum=0;
for(Integer num:nums ){
sum+=num;
}
return sum;
}
//将每一个组合转成String
public static String getNumbers(List<Integer> nums) {
StringBuilder sb = new StringBuilder();
for(Integer num:nums){
sb.append(num+" ");
}
return sb.toString();
}
}

复制代码

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

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

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

黑马程序员IT技术论坛 X3.2