七个用户确定的数，a,b,c,d,e,f,g，任选其中的m（1<=m<=7）个数，不重复选，求和sum，使sum<n，n是用户确定的一个数。
求所有可能的组合。
用户输入a,b,c,d,e,f,g和n，
程序输出多有可能的组合
可以换一个角度考虑，给定的数如果是M，那么针对数组中一个数字N，我们只需要查找一下数
组中是否含有M-N就可以了，这样就转换为数组查找问题了，然后可以利用空间换时间来搞
定，搞一个hash表，然后把每一个都映射到hash表中去，然后查找的时候就需要O(1)就可以
了，只不过空间复杂度达到O(N)
import java.util.Scanner;
/**
- 在一个无序的数组中，实现一个或者多个元素相加小于给定的目标数，所有的可能。 20C 数据结构 七个用户确定的数，a,b,c,d,e,f,g，任选其中的m（1<=m<=7）个数，不重复选，求和sum，使sum<n，n是用户确定的一个数。 求所有可能的组合。
用户输入a,b,c,d,e,f,g和n，
程序输出多有可能的组合
- @author * */ public class Test06 { public static void main(String[] args) { ImplementClass im = new ImplementClass(); im.implementMethod(); } } class ImplementClass{ public void implementMethod(){ Scanner sc = new Scanner(System.in); int[] arr = new int[7]; System.out.print("请输入7个确定的数(空格隔开)："); for(int i=0;i<arr.length;i++){ arr[i] = sc.nextInt(); } System.out.print("请输入m(1<=m<=7)："); int m = sc.nextInt(); System.out.print("请输入n："); int n = sc.nextInt();//最后比较大小的数 int count = 0; if(m == 1){ for(int a:arr){ if(implementMethod2(a)<n){ count++; huanHang(count); System.out.print(a+","); } } }else if(m == 2){ for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length;j++){ int temp = implementMethod2(arr[i],arr[j]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+","); } } } }else if(m == 3){ for(int i=0;i<arr.length-2;i++){ for(int j=i+1;j<arr.length-1;j++){ for(int k=i+2;k<arr.length;k++){ int temp = implementMethod2(arr[i],arr[j],arr[k]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+","); } } } } }else if(m ==4){ for(int i=0;i<arr.length-3;i++){ for(int j=i+1;j<arr.length-2;j++){ for(int k=i+2;k<arr.length-1;k++){ for(int l=i+3;l<arr.length;l++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+","); } } } } } }else if(m ==5){ for(int i=0;i<arr.length-4;i++){ for(int j=i+1;j<arr.length-3;j++){ for(int k=i+2;k<arr.length-2;k++){ for(int l=i+3;l<arr.length-1;l++){ for(int m2=i+4;m2<arr.length;m2++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l],arr[m2]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+" "+arr[m2]+","); } } } } } } }else if(m ==6){ for(int i=0;i<arr.length-5;i++){ for(int j=i+1;j<arr.length-4;j++){ for(int k=i+2;k<arr.length-3;k++){ for(int l=i+3;l<arr.length-2;l++){ for(int m2=i+4;m2<arr.length-1;m2++){ for(int n2=i+5;n2<arr.length;n2++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l],arr[m2],arr[n2]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+" "+arr[m2]+" "+arr[n2]+","); } } } } } } } }else if(m ==7){ for(int i=0;i<arr.length-6;i++){ for(int j=i+1;j<arr.length-5;j++){ for(int k=i+2;k<arr.length-4;k++){ for(int l=i+3;l<arr.length-3;l++){ for(int m2=i+4;m2<arr.length-2;m2++){ for(int n2=i+5;n2<arr.length-1;n2++){ for(int o=i+6;o<arr.length;o++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l],arr[m2],arr[n2],arr[o]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+" "+arr[m2]+" "+arr[n2]+" "+arr[o]+","); } } } } } } } } } System.out.println("\nm="+m+",n="+n+"的时候,可能的组合数"+count); } //输出6个组合换行 public void huanHang(int count){ if(count%7 == 0) System.out.println(); } public int implementMethod2(int...m){ int sum = 0; for(int temp:m){ sum += temp; } return sum; } }
可以把确定的数字组成数组，获取所有的数组组合,再挑选和符合条件的组合，这里介绍一下按位对应法来获取所有数组组合
final Integer[] arr = new Integer[] { 1, 2, 3, 5, 6, 7, 8 };
final int end = 1 << arr.length;
for (int start = 1; start < end; start++) {
int sum = 0;
final List<Integer> ls = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++) {
if (((1 << i) & start) != 0) {// 该位有元素输出
sum += arr[i];
ls.add(arr[i]);
}
}
if (sum < 7) {
System.out.println(Arrays.toString(ls.toArray()));
}
}