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

题目： 输入两个整数 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);
    }
}