学步园

100题之21题：编程求解，输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m。要求将所有的可能组合列出来。实际上就是一个背包问题。

求解思路：

1.首先判断，如果n>m，则n中大于m的数不可能参与组合，此时置n = m;

2.将最大数n加入且n == m,则满足条件，输出；

3.将n分两种情况求解，（1）n没有加入，取n = n - 1; m = m;递归下去；（2）n加入，取n = n - 1l, m = m - n,递归下去

public class s21 {<br /> private static LinkedList<Integer> list = new LinkedList<Integer>();<br /> /**<br /> * 求解思路：<br /> * 1.首先判断，如果n>m,则n中大于m的数不可能参与组合，此时置n=m；<br /> * 2.将最大的数n加入且n==m，则满足条件，输出；<br /> * 3.将n分两种情况求解：n没有加入，取n=n-1,m=m,递归；<br /> * 4.n加入，取n=n-1,m=m-n,递归。<br /> * 5.结束。<br /> * @param sum<br /> * @param n<br /> */<br /> public static void findSum(int sum, int n)<br /> {<br /> if ( n < 1 || sum < 1)<br /> return;<br /> if (sum > n)<br /> {<br /> list.add(n);<br /> findSum(sum - n, n - 1);// n加入，取n=n-1,m=m-n<br /> list.pop();<br /> findSum(sum, n - 1); // n没有加入，取n=n-1,m=m<br /> }<br /> else<br /> {<br /> System.out.print(sum); // sum < n ,直接输出n就可以满足了<br /> for (int i = 0; i < list.size(); i ++)<br /> System.out.print(" "+ list.get(i));<br /> System.out.println();<br /> }<br /> }<br /> /**<br /> * @param args<br /> */<br /> public static void main(String[] args) {<br /> // TODO Auto-generated method stub<br /> int sum = 10;<br /> int n = 6;<br /> findSum(sum,n);<br /> }<br /> }<br />