前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法-1到n中所有和为m的组合

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

作者头像
chaibubble
发布2018-01-02 11:43:13
1.8K0
发布2018-01-02 11:43:13
举报
文章被收录于专栏:深度学习与计算机视觉

题目: 输入两个整数 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]的情况,所有的递归就都结束了。

代码实现:

代码语言:javascript
复制
#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);
    }
}    
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-08-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档