欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

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

程序员文章站 2022-06-09 21:29:22
...

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?

  1. public class s21 {
  2. private static LinkedList list = new LinkedList();
  3. /**
  4. * 求解思路:
  5. * 1.首先判断,如果n>m,则n中大于m的数不可能参与组合,此时置n=m;
  6. * 2.将最大的数n加入且n==m,则满足条件,输出;
  7. * 3.将n分两种情况求解:n没有加入,取n=n-1,m=m,递归;
  8. * 4.n加入,取n=n-1,m=m-n,递归。
  9. * 5.结束。
  10. * @param sum
  11. * @param n
  12. */
  13. public static void findSum(int sum, int n)
  14. {
  15. if ( n 1 || sum 1)
  16. return;
  17. if (sum > n)
  18. {
  19. list.add(n);
  20. findSum(sum - n, n - 1);// n加入,取n=n-1,m=m-n
  21. list.pop();
  22. findSum(sum, n - 1); // n没有加入,取n=n-1,m=m
  23. }
  24. else
  25. {
  26. System.out.print(sum); // sum
  27. for (int i = 0; i
  28. System.out.print(" "+ list.get(i));
  29. System.out.println();
  30. }
  31. }
  32. /**
  33. * @param args
  34. */
  35. public static void main(String[] args) {
  36. // TODO Auto-generated method stub
  37. int sum = 10;
  38. int n = 6;
  39. findSum(sum,n);
  40. }
  41. }