小于等于n的正整数相加等于m的一个算法问题

Question

就是对任意的自然数n,m，取任意多个小于等于n的自然数相加，结果等于m，求所有的这种组合。

Answer 1

上面的算法会丢掉一些元素，造成输出的表达式不全。下面的算法用数组记住以输出的表达式，再加上每次迭代后的新表达式，就不会出现上面的问题。
public class Suanfa { /*
 * 有集合N={1,2,3……，n}，求a1+a2+……+aj=m(aj属于N)的所有组合，m,n都是自然数
 */
public static void func1(int n, int m, int k, int door, int[] a){
if(n>m) n = m;
if(m==1&&m>=k){
a[a.length-n]=1;
printA(a);
return;
}else if(n==1){
if(m<=door){
a[a.length-n]=m;
printA(a);
}
return;
}else {
int i = 0;
while(n*i<=m){
if(i>=k){
if(i>0)
a[a.length-n]=i;
func1(n-1,m-i,i,door,a);
}
i++;
}
}
}
public static void printA(int[] a){
for(int i = 0; i < a.length; i++){
if(a[i]>0&&i!=a.length-1){
System.out.print(a[i]+"+");
}else if(a[i]>0){
System.out.print(a[i]);
}
}
System.out.println();
}
public static void main(String[] args) {
//func1_1(6,6,0,6);
func1(3,6,0,3,new int[3]);
}}

Answer 2

a1  a2   a3.
0   0     0
0   0     1
0   1     0二进制

Answer 3

我感觉这个问题可以用递归求解。
将问题转换成减法 先求  m-a1是否在数组n中。如果存在ak = m-a1 则 a1+ak=m成立。接下来求解 a1-a2是否存在数组中，如果存在aj = a1-a2,则aj+a2+ak也成立。以此类推。

Answer 4

你这个想法就是将m分为aj+ak,然后将aj和ak分别再如此往下分为aj'、aj''和ak'、aj''，如m=6=2+4=1+1+4=2+1+3等。
如果这样的话不好去重。

Answer 5

你这个想法就是将m分为aj+ak,然后将aj和ak分别再如此往下分为aj'、aj''和ak'、aj''，如m=6=2+4=1+1+4=2+1+3等。
如果这样的话不好去重。嗯，确实存在解集重复的问题。
要完成去重的话，就需要做一些其他操作了。对每一个解集做排序，然后存Set。