算法-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 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

技术 | Python从零开始系列连载(二十四)

为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

592
来自专栏calmound

HDU 1024 Max Sum Plus Plus

http://acm.hdu.edu.cn/showproblem.php?pid=1024 题意:可不连续的m个子段的最大和 分析:首先由于n很大,所以需要运...

2674
来自专栏aCloudDeveloper

LeetCode:5_Longest Palindromic Substring | 最长的回文子串 | Medium

题目: Given a string S, find the longest palindromic substring in S. You may assum...

19210
来自专栏数据结构与算法

#15. 钻石

钻石 diamond.in/.out/.cpp 【问题描述】 你有 n 个 “量子态” 的盒子,每个盒子里可能是一些钱也可能是一个钻 石。 现在你知道如果打开第...

2626
来自专栏落影的专栏

程序员进阶之算法练习(十七)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 如何从这篇文章受益? 先看题目大意,对照Example的样...

4109
来自专栏郭耀华‘s Blog

有效防止softmax计算时上溢出(overflow)和下溢出(underflow)的方法

《Deep Learning》(Ian Goodfellow & Yoshua Bengio & Aaron Courville)第四章「数值计算」中,谈到了...

2764
来自专栏海天一树

小朋友学C语言(4):单精度浮点数与双精度浮点数

上节课 简单介绍了浮点数。计算机程序中的浮点数分为单精度浮点数和双精度浮点数。 单精度和双精度精确的范围不一样。 计算机里的最基本的存储单位用位(bit)来表...

33412
来自专栏WD学习记录

牛客网 数字游戏

小易邀请你玩一个数字游戏,小易给你一系列的整数。你们俩使用这些整数玩游戏。每次小易会任意说一个数字出来,然后你需要从这一系列数字中选取一部分出来让它们的和等于小...

671
来自专栏小樱的经验随笔

洛谷P1313 计算系数【快速幂+dp】

P1313 计算系数 题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数。 输入输出格式 输入格式: 输入文件名为facto...

1985
来自专栏聊聊技术

原 "二分查找(Binary Search

41511

扫码关注云+社区