算法-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);
    }
}    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

3502
来自专栏魂祭心

原 canvas绘制clock

5934
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2997
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

3277
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

46210
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

4525
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

4789
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

3356
来自专栏菩提树下的杨过

Flash/Flex学习笔记(23):运动学原理

先写一个公用的小球类Ball: package{ import flash.display.Sprite; //小球 类 public class B...

28610
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.6K7

扫码关注云+社区