输入两个整数n和m, 从数列1,2,...,n中任意选择几个数,使其和等于m, 要求编写程序输出所有的组合输入两个整数n和m, 从数列1,2,...,n中任意选择几个数,使其和等于m, 要求编写程序输出所有的组合
我觉得跟n没多大关系，只要n>m就可以了。举个例子，例如n=100，m=10
则组合包括
[1,9]
[1,2,7]
[1,2,3,4]
[1,3,6]
[1,4,5]
[2,8]
[2,3,5]
[3,7]
[4,6]
为了避免[1,9]和[9,1]的重复，我们保证分割时左边小于右边的数。
其实这个是一个递归切割的问题。
例如10被分割成[1,9],我们就继续把9进行分割，为了避免与前面的1重复，我们对9从2开始分割。于是把9分割成[2,7],然后对7进行分割，为了保证不与2冲突，我们从3开始分割。。。以此类推。
1.每个数都要一个最小的开始分割点，例如[1,9]后，9从2开始分割。
2.要保证分割的数左边小于右边。
看看下面纯自己撸的代码
public static void main(String[] args) throws InstantiationException, IllegalAccessException {
ArrayList<Integer> input=new ArrayList<>();
getZhuhe(input,1,10,5);
}
//input是输入的前置数组，start是开始分割的数字，max是最大值
public static void getZhuhe(ArrayList<Integer> input,int start,int num,int max) {
if(num>max){
System.out.println("this can never done!!");
return;
}
int rest=0;
ArrayList<Integer> tempinput = new ArrayList<>();
for(int i=start;i<num-i;i++){
tempinput.clear();
tempinput=(ArrayList<Integer>) input.clone();
rest=num-i;
tempinput.add(i); //保存前置数组
for (int j = 0; j < tempinput.size(); j++) {
System.out.print(" "+tempinput.get(j)); //打印前置数组
}
System.out.print(" "+rest); //打印最后的一个值
System.out.println("");
getZhuhe(tempinput,i+1, rest,max); //递归求值
}
}
补丁:###
一位热心观众给我留言，指出我的问题了，我更正下
楼主,n<m的情况也可以把，例如n=5，m=10时，
n{1,2,3,4,5}
例如 5,3,2 或者5,4,1之类的都可以吧。下面程序我是按照这种情况写的，你学习下罗
public static void getshuzuhe(int max,int targesum){
int sum1=0; //第一轮加的和
int sum2=0; //第二轮加的和
ArrayList<Integer> arr1;
ArrayList<Integer> arr2;
for (int i=max;i>0;i--){ //从大往小的方向加
sum1=0;
arr1=new ArrayList<Integer>();
if(sum1+i>targesum){
continue; //第一轮就大于目标targesum，直接跳过。例如如果targesum=10，max=100，那第一轮就不合适了
}else {
sum1=sum1+i;
arr1.add(i);
sum2=sum1; //初始化第二轮的和值
arr2=(ArrayList<Integer>) arr1.clone();
}
for(int j=i-1;j>0;j--){
if(sum2+j>targesum){
continue;
}else if(sum2+j<targesum){
sum2=sum2+j; //还没达到targesum，继续加
arr2.add(j); //保存下值
}else if(sum2+j==targesum){
arr2.add(j); //达到target sum了.显示出来
System.out.print("{");
for (int k = 0; k < arr2.size(); k++) {
System.out.print(" "+arr2.get(k));
}
System.out.print(" }");
System.out.println(" ");
arr2.clear(); //清除下数组
sum2=sum1; //初始化和值，例如7，3找到了，还要找7，2，1呢。数组要出事话为7呢
arr2=(ArrayList<Integer>) arr1.clone(); //初始化数组
}
}
}
}
又有一个热心观众说用递归的方法，怎么递归呢？不断地切割sum值和n值。
import java.util.LinkedList;
public class ShenZhen {
private static LinkedList<Integer> templist = new LinkedList<Integer>();
/**
* @param sum
* @param n
*/
public static void findSum(LinkedList<Integer> templist,int sum, int n)
{
LinkedList<Integer> inputlist = null;
LinkedList<Integer> outputlist = null;
inputlist=(LinkedList<Integer>) templist.clone(); //每次递归输入
outputlist=(LinkedList<Integer>) templist.clone(); //每次递归输出
System.out.println("sum="+sum+" n="+n);
if(n<1 && sum!=n){
System.out.print("not found!!");
//list.clear();
return;
}
if(sum > n){ //sum大于n，要编译每个n
for(int i=n;i>0;i--){
outputlist=(LinkedList<Integer>) inputlist.clone();
outputlist.push(i);
System.out.println("push "+i);
findSum(outputlist,sum-i, i-1);
}
}else if(sum == n){ //sum等于n，找到了
outputlist.push(n);
System.out.println("push "+n);
System.out.print("****************find it !!");
for (int i = 0; i < outputlist.size(); i ++)
System.out.print(" "+ outputlist.get(i));
}else if(n > sum){ //sum小于n，直接push sum值，但这个sum值可能可以再切分，要pop出来，在切分，例如7，3.。就要把3pop出来先，然后在分3，得到2,1
outputlist.push(sum);
System.out.println("push "+sum);
System.out.print("*********************find it !!");
for (int i = 0; i < outputlist.size(); i ++)
System.out.print(" "+ outputlist.get(i));
System.out.println();
System.out.println("pop "+outputlist.pop());
findSum(outputlist,sum, sum-1);
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int sum = 30;
int n = 20;
findSum(templist,sum, n);
}
}
切割sum值递归.png
