100题之21题：编程求解，输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m。要求将所有的可能组合列出来。实际上就是一个背包问题。 求解思路： 1.首先判断，如果nm，则n中大于m的数不可能参与组合，此时置n = m; 2.将最大数n加入且n == m,
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,递归下去
[java] view plaincopyprint?
- public class s21 {
- private static LinkedList
list = new LinkedList(); - /**
- * 求解思路：
- * 1.首先判断，如果n>m,则n中大于m的数不可能参与组合，此时置n=m；
- * 2.将最大的数n加入且n==m，则满足条件，输出；
- * 3.将n分两种情况求解：n没有加入，取n=n-1,m=m,递归；
- * 4.n加入，取n=n-1,m=m-n,递归。
- * 5.结束。
- * @param sum
- * @param n
- */
- public static void findSum(int sum, int n)
- {
- if ( n 1 || sum 1)
- return;
- if (sum > n)
- {
- list.add(n);
- findSum(sum - n, n - 1);// n加入，取n=n-1,m=m-n
- list.pop();
- findSum(sum, n - 1); // n没有加入，取n=n-1,m=m
- }
- else
- {
- System.out.print(sum); // sum
- for (int i = 0; i
- System.out.print(" "+ list.get(i));
- System.out.println();
- }
- }
- /**
- * @param args
- */
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- int sum = 10;
- int n = 6;
- findSum(sum,n);
- }
- }
