给大家伙搞点题来做做

Question

现在给定一个数n,请列出1--(n-1)范围内，所有和为n的组合（数字不能重复使用），比如：n = 10时，
1+9 = 10;
2+8 = 10;
3+7 = 10;
1+2+3+4 = 10;
.......

Answer 1

另外给大伙看点东西，我被人BS了http://topic.csdn.net/u/20110730/16/45d59184-d2d5-46c9-ad13-a974ac34e266_2.html?seed=1680385609&r=74700354#r_74700354

Answer 2

public class Add20 {
public static List<List<Integer>> getArrange(int begin, int end, int sum) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (begin>end) return result;
if (begin>sum/2) {
if (sum>=begin && sum<=end) {
result.add(new ArrayList<Integer>());
result.get(0).add(sum);
}
return result;
}
List<List<Integer>> l1 = getArrange(begin+1, end, sum-begin);
for (int i=0; i<l1.size(); i++) l1.get(i).add(0, begin);
result.addAll(l1);
result.addAll(getArrange(begin+1, end, sum));
return result;
} public static void main(String[] args) {
List<List<Integer>> list = getArrange(1,20,20);
System.out.println(list.size() + "种组合:");
for (int i=0; i<list.size(); i++)
System.out.println(list.get(i));
}
}

Answer 3

给大家提供个pku acm里的题，虽然题不一样，算法和楼主的题相似。
这个题的算法可以解决更广级别的问题，楼主的题目是这个解法中的一个情况。Description
 
 乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，
 但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。
 Input
 
 输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。
 在最后一组数据之后，是一个零。
 Output
 
 为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。 
 Sample Input
 
 9
 5 2 1 5 2 1 5 2 1
 4
 1 2 3 4
 0
 
 Sample Output
 
 6
 5

Answer 4

这个问题早有人问过了
http://topic.csdn.net/u/20110728/17/cdc061d8-36da-4356-b578-fd5a5274a078.html
http://topic.csdn.net/u/20110610/18/171d6808-fd2c-429c-932b-2c7ee018ea80.html
http://topic.csdn.net/u/20110608/23/70ca1838-1697-497f-9cf8-a61f33116c9a.html凑个热闹吧
import java.util.*;
class Analyzer {
    public static void main(String[] args) {
        int n = 10;
        for (int i=1; i<n; i++) {
            analyze(n, i, false); //false数字不重复，true数字可重复
        }
    }
    
    public static void analyze(int sum, int num, boolean dup) {
        if (num >= sum) {num = sum-1;}
        if (num < 2) {
            System.out.printf("%d=%d\n", sum, sum);
            return;
        }
        
        int tmp = 0, row = 0;
        int[] idx = new int[num];
        for (int i=0; i<num-1; i++) {
            if (dup) {
                idx[i] = 1;
            } else {
                idx[i] = i+1;
            }
            tmp += idx[i];
        }
        idx[num-1] = sum-tmp;
        if (!dup) {
            if (idx[num-1] <= idx[num-2]) {return;}
        } else {
            if (idx[num-1] < 0) {return;}
        }        for (int i=0; i<num-1; i++) {
            System.out.printf("%d+", idx[i]);
        }
        System.out.printf("%d=%d\n", idx[num-1], sum);        while (true) {
            idx[num-2]++;
            for (int i=num-2; i>0; i--) {
                tmp = 0;
                for (int j=0; j<i; j++) {tmp+=idx[j];}
                if (idx[i] > (sum-tmp)/(num-i)) {
                    idx[i-1]++;
                }
            }
            if (idx[0] > sum/num) {break;}
            
            tmp = 0;
            for (int i=1; i<num-1; i++) {
                tmp += idx[i-1];
                if (idx[i] > (sum-tmp)/(num-i)) {
                    if (dup) {
                        idx[i] = idx[i-1];
                    } else {
                        idx[i] = idx[i-1]+1;
                    }
                }
            }
            tmp = 0;
            for (int i=0; i<num-1; i++) {
               tmp += idx[i];
            }
            idx[num-1] = sum-tmp;
            if (!dup) {
                if (idx[num-1] <= idx[num-2]) {continue;}
            } else {
                if (idx[num-1] < 0) {continue;}
            }
            
            for (int i=0; i<num-1; i++) {
                System.out.printf("%d+", idx[i]);
            }
            System.out.printf("%d=%d\n", idx[num-1], sum);
        }
    }
}