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

相关文章

来自专栏null的专栏

挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是...

3364
来自专栏人工智能LeadAI

算法 | 数据结构常见的八大排序算法

01 前言 八大排序,三大查找是《数据结构》当中非常基础的知识点,在这里为了复习顺带总结了一下常见的八种排序算法。 常见的八大排序算法,他们之间关系如下: ...

2704
来自专栏我是攻城师

理解插入排序,希尔排序,选择排序的算法原理

在前面的文章中,其实已经把效率比较高的排序算法给分析过了,比如比较通用的快排,归并排序和堆排,还有用于特定场景的计数排序等。本篇我们把剩下的几种效率一般的排序算...

501
来自专栏我是东东强

常见算法之排序

各类排序算法,不仅是算法基本功,也是面试中永恒的考题,关于每种算法思想、实现(递归与非递归)以及时空复杂度分析是必须牢牢把握的送分题。本文先将排序算法按不同标准...

872
来自专栏专注 Java 基础分享

面试中常用排序算法实现(Java)

     当我们进行数据处理的时候,往往需要对数据进行查找操作,一个有序的数据集往往能够在高效的查找算法下快速得到结果。所以排序的效率就会显的十分重要,本篇我们...

2289
来自专栏人工智能LeadAI

排序算法:Python 实现

import sys print (sys.version) # 3.5.2 |Continuum Analytics, Inc.| (default, J...

34710
来自专栏架构师小秘圈

秒懂排序算法

作者:郭耀华,来自:cnblogs.com/guoyaohua 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳...

3635
来自专栏刘望舒

算法(三)初等排序后篇[选择和希尔排序]

1.选择排序 根据上一篇文章讲到的插入排序和冒泡排序,我们把选择排序的数组也分为已排序部分和未排序部分。 图解选择排序 在用图来讲解选择排序之前,我们要先了...

1728
来自专栏Java Edge

八大排序的Java实现概述1. 插入排序—直接插入排序(Straight Insertion Sort)2. 插入排序—希尔排序(Shell`s Sort)4. 选择排序—堆排序(Heap Sort)

3216
来自专栏Android机器圈

数据结构与算法 -- 二叉树链式详解((非)/递归遍历,叶子个数,深度计算)

PS:树型结构是一种重要的非线性数据结构,教科书上一般都是树与二叉树,由此可见,树和二叉树是有区别和联系的,网上有人说二叉树是树的一种特殊形式,但经过查资料,树...

575

扫码关注云+社区