一个算法的实现，100以内所有可以加为100的整数的组合

Question

要求数字不重复，组合不重复（无视次序）
例如：
1+99
1+2+97
1+2+3+94
…欢迎大家一起讨论一下算法的实现方式

Answer 1

用递归写了一个结果发现100这个数太大，导致全排列当机，立即关掉eclipse
惭愧。明天有时间再重写，不用递归了，栈不够用。
另外有那位兄弟把高中课本上的全排列和组排列计算公式发来，温故下
我记的全排列是n！个
组排列是n!/(n*(n-1)!) 个
不知道上面写的对不对，记不住了，太多年了。
算法题一般会比较火，这点楼主可以放心。

Answer 2

组排列是n!/(n*(n-1)!) 个 
晕，这个肯定不对了
狂晕。太晚了，还是睡觉吧。

Answer 3

我就用递归
99+1
=97+(2+1) // (97+2)+1
=94+3+2+1
...
x1,x2,x3,...1直到x1<=x2返回。拆分方法：x1 = (x2+1)+Y 成功么？ 
Y不能是x2,x3,...1 或者 Y >= (x2+2)基本差不多了，好像不太难。
排列组合我不用，计算机穷举吧，然后输出格式弄下就可以了吧。

Answer 4

当然，第一个执行的为(100,0),每成功时就保留或输出。什么printf(),System.out.println(),Control.WriteLine()
哎~~~ 语言都虚的，没什么大用，原理，框架，算法才是根本。
就当发发牢骚了，呵呵~~~据说window7也快出来了。
搞那么多系统，有什么必要吗？？？ vista估计没几人装过吧。

Answer 5

KAO，有打乱队形，影响解决问题的嫌疑
我靠边，我靠边
大家继续
个人浮浅的同意6楼的

Answer 6

KAO，有打乱队形，影响解决问题的嫌疑
我靠边，我靠边
大家继续
个人浮浅的同意6楼的

Answer 7

public static void cha(int n, String str) {
for (int i = 1 ; i <= n / 2; ++i) {
System.out.println(str + i + "+" + (n - i));
if (!ab[n - i]) {
ab[n - i] = true;
cha(n-i,str + i + '+');
}
}
}
記得昨天有個人問一個相同的問題,我看到後一直想,至到乘車回家時想到了這個方法,但100的輸出結果太大,你改用文件outputstream來保存吧,我的思路可以從代碼看出,對錯與否請告訴我一聲

Answer 8

還有,ab是一個boolean[n + 1]型的,ab[1]初始化為true,其餘為false

Answer 9

递归实现： public static void main(String[] args) {
split(100,0,"");
}
public static void split(int n,int base,String result){
if(n==0){
System.out.println(result);
return;
} for(int i=base+1;i<=n;i++){
split(n-i,i,result+i+"|");
}
}

Answer 10

这是我的实现，不过看起来结果集好大啊。
[Code==JAVA]
public class Combination {
public static void main(String[] args) {
int[] src = new int[100];
for(int i=1; i<=100; i++){
src[i-1] = i;
}
Combination c = new Combination(src, 100);
c.getResult();
}

private int[] candidates = null;
private int target = 0;

public Combination(int[] cand, int target){
this.candidates = cand;
this.target = target;
}

public void getResult(){
for(int i=0; i<candidates.length; i++){
if(candidates[i]==target){
System.out.println(""+candidates[i]+"="+target);
}
explore(new int[]{candidates[i]}, i+1);
}
}

public void explore(int[] curr, int i){
for(int j=i; j<candidates.length; j++){
if(sun(curr)+candidates[j]==target){
printResult(curr, candidates[j]);
}else if(sun(curr)+candidates[j]<target){
int[] curr2 = new int[curr.length+1];
System.arraycopy(curr, 0, curr2, 0, curr.length);
curr2[curr2.length-1] = candidates[j];
explore(curr2, j+1);
}
}
}

public int sun(int[] arr){
int sun = 0;
for(int i=0; i<arr.length; i++){
sun += arr[i];
}
return sun;
}

public void printResult(int[] curr, int last){
for(int i=0; i<curr.length; i++){
System.out.print(""+curr[i]+"+");
}
System.out.print(""+last+"=");
System.out.println(target);
} }
[/Code]

Answer 11

/*
 * 100可分解为1+99，99又可继续分解。
 * 因为用的是1和99分解。所以分解99从1+1开始。2+?
 */
public class Main {    public static void main(String[] args) {
        new Main().start(10);
    }    private void start(int a) {
        n = a;
        iarr = new int[(int) Math.sqrt(n * 2)];
        for (int i = 1; i < n; i++) {
            iarr[0] = i;
            k = 1;
            sum = i;
            g();
        }
        System.out.println("_________________" + s);
    }    public void g() {
        if (n - sum <= 0) {
            System.out.print(iarr[0]);
            for (int i = 1; i < k; i++) {
                System.out.print("+" + iarr[i]);
            }
            System.out.println();
            s++;
            return;
        }
        for (int i = iarr[k - 1] + 1; i <= n - sum; i++) {
            iarr[k++] = i;
            sum += i;
            g();
            sum -= i;
            k--;
        }
    }
    private int n;
    private int k;
    private int sum;
    private int s;
    private int[] iarr;
}

Answer 12

public void go(){
   String res="";
   addTo(1,res,100);
   }
   public void addTo(int base,String res,int leftValue){
   if(leftValue==0){
   System.out.println(res);
   return;
   }
   for(int i=base;i<leftValue;i++){
   addTo(i+1,res+"+"+(i+1),leftValue-i-1);
   }
   }不知道对不对

Answer 13

1L：可以用20测试，组排列的话，应该还要判断求和
5L：竹子的组合有重复。。
6L：看11L
12L：重复
16,17,19L：用20测试看，都是正确的结果
20L：代码addTo(0,res,100);也是正确的结果欢迎大家继续讨论，能从算法分析角度来说最好。
最近笔试的，跳槽的多，看下算法也算造福广大java同胞  =。=

Answer 14

整理了16楼的算法，这个递归深度是可控的
感谢jayflee， 
100以内可以累加为100的整数组合

Answer 15

public class T {

private int[] nums = new int[100];

public void step(int a0, int max, int sum, int step){
if(a0 == sum){
for(int i = 0; i < step; i++){
System.out.print(nums[i] + ", ");
}
System.out.println(sum);
return;
}
if(a0 > sum / 2)
return;
for(int i = a0; i <= max && i <= sum; i++){
nums[step] = i;
step(i + 1, max, sum - i, step + 1);
}
} public static void main(String[] args) {
T t = new T();
t.step(1, 100, 1000, 0);
}
}