输入两个整数n和m，从数列1,2,3，……n中随意取几个数，使其和等于m

题目：编程求解，输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m。要求将所有的可能组合列出来。

分析：分治的思想。可以把问题(m,n)拆分(m - n, n -1)和(m, n - 1)。

注意点：1、n大于m时，可直接从n = m出开始搜索

　　　　2、结束条件：n < 1 || m < 1

　　　　3、打印输出结果。注意打印输出结果并不代表函数调用结束，以n = 7 和 m = 10为例，7、3和7、2、1都是一种结果，不能得到7、3的时候终止。打印输出的条件是n = m

程序代码如下：

Java

public class FindSum {

    // used as a stack to save the result

    private static LinkedList<Integer> list = new LinkedList<Integer>();

    public static void findSum(int sum, int n) {

        if (n < 1 || sum < 1)

            return;

        if (sum < n)

            n = sum;

        if (sum == n) {

            for (int i = 0; i < list.size(); i++)

                System.out.print(list.get(i) + " ");

            System.out.print(sum);

            System.out.println();

        }

        list.addLast(n);

        findSum(sum - n, n - 1);

        list.removeLast();

        findSum(sum, n - 1);

    }

    public static void main(String[] args) {

        int sum = 10;

        int n = 8;

        findSum(sum, n);

    }

}