算法--中兴面试：输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数, 使其和等于 m

待我称王封你为后i 2022-06-12 03:46 182阅读 0赞

转载请注明原文出处：[http://blog.csdn.net/baidu\_37107022/article/details/75125846][http_blog.csdn.net_baidu_37107022_article_details_75125846]

# **Q题目** #

**编程求解**

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

--------------------

# **Answer解法** #

这道题就是一道典型的动态规划问题了，思路和背包问题差不多，m就相当于背包能容纳的重量了，就是从右往左校验，通过m，以及m-n进行下一次计算。

## **2.1 逻辑分析** ##

1.  首先判断，如果n>m，则n中大于m的数不可能参与组合，此时置n = m;
2.  将最大数n加入且n == m,则满足条件，直接输出；
3.  将n分两种情况求解
    
    （1）n没有加入，取n = n-1; m = m;递归下去  
    （2）n加入，取n = n-1, m = m-n,递归下去

**当前是 ：**  printList( m , n )

**递归下一层是 ：**  printList( m , n-1 ) 和 printList( m-n , n-1 )

printList(m,n)=printList(m,n−1)\+printList(m−n,n−1)；

**终止条件**：n<=0，以及m<0(m<0说明在上一次递归调用是减的n，结果减多了，所以为负)，m==0时候说明正好找到，打印

## **2.2代码实现** ##

package 中兴面试;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 2010 年中兴面试题 编程求解： 输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数, 使其和等于 m
     * ,要求将其中所有的可能组合列出来.
     */
    public class Test {
        
        public static void main(String[] args) {
            int n = 7;
            int m = 8;
            List<Integer> list = new ArrayList<>();
            // 1.首先判断，如果n>m，则n中大于m的数不可能参与组合，此时置n = m;
            int up = n > m ? m : n;
    
            printList(m, up, list);
        }
    
        /**
         * 
         * @param m
         *            要求满足的和sum
         * @param n
         *            取数的范围scope
         * @param list
         *            每一种满足条件的组合
         */
        public static void printList(int m, int n, List<Integer> list) {
            // m=0时，即背包刚好装满，打印并退出
            if (m == 0) {
                System.out.println(list);
                return;
            }
    
            // 根据题意，可知m和n必须为正整数，所以m和n为负数，或n=0时，直接退出
            if (n <= 0 || m < 0) {
                return;
            }
    
            // 拿到上一次计算的结果list
            List<Integer> list1 = new ArrayList<Integer>(list);
    
            // n没有加入
            printList(m, n - 1, list);
    
            // n加入
            list1.add(n);
            printList(m - n, n - 1, list1);
        }
    }

**测试结果：**

![这里写图片描述][SouthEast]

若不懂动态规划算法，可参考[http://blog.csdn.net/baidu\_37107022/article/details/73188963][http_blog.csdn.net_baidu_37107022_article_details_73188963]

[http_blog.csdn.net_baidu_37107022_article_details_75125846]: http://blog.csdn.net/baidu_37107022/article/details/75125846
[SouthEast]: /images/20220612/e6d92d1f8506458ea78a2c5bbe0d38ad.png
[http_blog.csdn.net_baidu_37107022_article_details_73188963]: http://blog.csdn.net/baidu_37107022/article/details/73188963