算法-1到n中所有和为m的组合

旧城等待， 2022-06-10 09:22 219阅读 0赞

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

**解题思路：**  
好未来笔试题中的一道题目，是背包问题的一个衍生问题，设i是1，2，3…….n 中的一个数，那么从i=1开始，（n，m，i）的问题就可以变成（n，m-i，i+1）的子问题，依次递归下去，这样会有两个结果，一个是m被减成了0，一个是i比m大甚至i比n大。出现前者时，满足条件的一组结果就找到了，而后者做为某一层递归退出的条件。举个例子，假设n=3，m=4，i的初始值为1，组合结果为v：  
调用函数：（3，4，1） v\[1\]  
第一层递归：（3，3，2） v\[1，2\]  
第二层递归：（3，1，3） i>m 退回到第一层  
第一层递归：（3，3，3） v\[1，3\]  
第二层递归：（3，0，4） m=0 找到满足条件的一组数 退回到第一层，且i>m 退回到第一层  
第一层递归：（3，3，4） v\[1，4\] i>m 退回到第0层  
调用函数：（3，4，2） v\[2\]  
.  
.  
.  
直到在第0层的时候，i>n,即 v\[3\]的情况，所有的递归就都结束了。

**代码实现：**

#include "iostream"    
    #include<vector>
    using namespace std;
    void Combination(int n, int m, vector<int>& v, int beg) 
    {
        if (m == 0) 
        {
            for (int i = 0; i<v.size(); i++)
            {
                i == 0 ? cout << v[i] : cout << " " << v[i];
            }
            cout << endl;
        }
        for (int i = beg; i <= n&&i <= m; i++)
        {
            v.push_back(i);
            Combination(n, m - i, v, i + 1);
            v.pop_back();
        }
    }
    int main()
    {
        int n, m;
        while (cin >> n >> m) 
        {
            if (n<1)
            return 0;
            vector<int>v;
            Combination(n, m, v, 1);
        }
    }