【nowcoder】求和

题目描述

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

解决思路

基于递归实现dfs(深度优先搜索) 即可. 这是一个比较典型的背包问题.
背包问题的一个衍生问题，设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

调用函数：   （3,4,1）v[1]
①第一层递归：（3,3,2） v[1,2]
②第二层递归：（3,1,3） v[1,2] i大于m退回到第一层
③第一层递归：（3,3,3） v[1,3]
④第二层递归：（3,0,4） v[1,2]  m=0满足条件的一组数，退回到第一层，且r>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){
// m == 0 为递归结束条件. 此时 v 中可能已经包含了若干个元素了. 并且 v 中的内容就是一组结果.
    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++){
    // 以下几行代码是该题目的关键. 问题的转换.
    // 为了求 i -> n 有多少种情况和为 m, 则把问题转换为
    // i + 1 -> n 有多少中情况和为 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);
        
    }
    return 0;
}