黑马程序员技术交流社区

标题: 在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 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集合。
代码实现如下：

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