《算法竞赛进阶指南》-AcWing-93. 递归实现组合型枚举-题解_Tisfy的博客-程序员秘密

技术标签: 题解  # 《算法竞赛进阶指南》  # AcWing  

递归实现组合型枚举

传送门

问题描述

1 ∼ n 1\sim n 1n的整数中选出 m m m个,输出所有的选择方案。

输出格式:对于每种方案,从小到大空格隔开;对于不同的方案,字典序升序输出。

数据范围

  • n > 0 n>0 n>0
  • 0 ≤ m ≤ n 0≤m≤n 0mn
  • n + ( n − m ) ≤ 25 n+(n−m)≤25 n+(nm)25

输入样例

5 3

输出样例

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

解题思路

类似于递归实现指数型枚举,我们只需要在选取数量恰好是 m m m的时候再输出就行了。

但是需要注意的是,数据范围变成了25。所以需要剪枝,即在已经不可能达到最终结果的时候提前退出递归。

这一题如果选取的元素已经大于 m m m个了,就不可能正好选 m m m个了,就需要退出。同理,如果所选元素的个数加上剩下的所有元素也达不到 m m m,也需要退出。

如果把上一题的代码直接搬过来,加上剪枝,就是:
错误示范:

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
vector<int>v;
int n,m;
void prt()
{
    
    for(int i=0;i<v.size();i++)
        printf("%d ",v[i]);
    puts("");
}
void calu(int x)
{
    
    if(x>n)return x==n+1&&v.size()==m?prt():void();
    if(v.size()>m||v.size()+(n-x+1)<m)return;
    calu(x+1);
    v.push_back(x);
    calu(x+1);
    v.pop_back();
}
int main()
{
    
    cin>>n>>m;
    calu(1);
    return 0;
}

运行会发现结果是倒序的,大的结果在前面

3 4 5 
2 4 5
2 3 5
2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3

这是由 我们先不选第 x x x个元素再选第 x x x个元素 造成的。

calu(x+1);
v.push_back(x);
calu(x+1);
v.pop_back();

而第 x x x个元素是比较小的(从小到大递归),本来应该在前面才对。

所以我们只需要调整一下pushpop的顺序即可。

总的就为:

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
vector<int>v;
int n,m;
void prt()
{
    
    for(int i=0;i<v.size();i++)
        printf("%d ",v[i]);
    puts("");
}
void calu(int x)
{
    
    if(x>n)return x==n+1&&v.size()==m?prt():void();
    if(v.size()>m||v.size()+(n-x+1)<m)return;
    v.push_back(x);
    calu(x+1);
    v.pop_back();
    calu(x+1);
}
int main()
{
    
    cin>>n>>m;
    calu(1);
    return 0;
}

原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/119254698

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Tisfy/article/details/119254698

智能推荐

flutter ---TextField 之 输入类型、长度限制_一个flutter大菜鸟的博客-程序员秘密_flutter 输入框限制长度

TextField想要实现输入类型、长度限制需要先引入import ‘package:flutter/services.dart’;例如import 'package:flutter/services.dart';TextField( keyboardType: TextInputType.number,//键盘类型,数字键盘 style: TextStyle(...

Shader基本概念_屠变恶龙之人的博客-程序员秘密

以下内容不需要入门的时候立刻阅读和理解,建议逐渐深入学习后,不时回来看看即可。什么是GPU?GPU:Graphic Processing Unit,中文翻译为“图形处理器”。显卡包括(GPU,显存,显卡BIOS,显卡PCB板)。什么是Shader?Shader程序:GPU执行的,针对3D对象进行操作的程序。Shader有哪几种?CG:与DirectX 9.0

【Oracle】ORA-14758: Last partition in the range section cannot be dropped_Alen_Liu_SZ的博客-程序员秘密_ora-14758

目录1 软件环境2 问题模拟2.1 新建分区表2.2 初始化数据2.3 查看分区信息2.4 删除分区P13 问题分析与解决3.1 ORA ERR分析3.2 问题解决最近做数据库上线脚本的评审时,开发人员遇到了ORA-14758错误,本篇就针对这一错误进行分析,并给出解决方案。1 软件环境本实验的演示环境如下:SQL&gt; SELECT * f...

LiveNVR监控流媒体Onvif/RTSP功能-接收无人机、IPC等设备RTMP推流转码分发WEB视频播放也可以GB28181输出_Marvin1311的博客-程序员秘密_onvif推流

LiveNVR功能-接收无人机、IPC等设备RTMP推流转码分发WEB视频播放也可以GB28181输出1、无人机推流转国标2、获取RTMP推流地址2.1、RTMP推流地址格式2.2、推流地址示例2、设备RTMP推流3、配置拉转RTMP3.1、直播流地址格式3.2、直播流地地址示例3.3、通道配置直播流地址4、推流并发多时处理5、配置级联到GB28181国标平台6、非国标直播流转GB28181服务搭建1、无人机推流转国标目前不是所有的无人机都支持GB28181的国标注册,有的只能输出直播流,有的只能支持R

Win10报错:找不到gpedit.msc(或 secpol.msc)_蓝多多的小仓库的博客-程序员秘密_找不到secpol.msc

报错:找不到gpedit.msc(或 secpol.msc)原因:Win10的Home版没有secpol.msc和gpedit.msc,无法更改本地策略的相关设置。解决方案:1、新建文本文档并复制如下内容@echo offpushd "%~dp0"dir /b C:\Windows\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum &g...

用C语言做一个横板过关类型的控制台游戏_weixin_34352449的博客-程序员秘密

前言:本教程是写给刚学会C语言基本语法不久的新生们。因为在学习C语言途中,往往只能写控制台代码,而还能没接触到图形,也就基本碰不到游戏开发。所以本教程希望可以给仍在学习C语言的新生们能提前感受到游戏开发技术的魅力和乐趣。先来看看本次教程程序大概的运行画面:游戏循环机制下面是一个简单而熟悉的C程序。#include &lt;stdio.h&gt;int main() { ...

随便推点

Ubuntu 18.04中安装VMware14.1.0踩坑_fantasyagain的博客-程序员秘密

Ubuntu 18.04中安装VMware14.1.0踩坑96 GodfansMa2018.09.04 10:50* 字数 465 阅读 88评论 0喜欢 1转载自: https://www.jianshu.com/p/5fc43bbbac5a如果只想快速安装VMware 请直接看文章最后。一、网上找了14.1.0的破解安装包,下载地址如下:https://www.macxin.com...

nn.Sequential()和nn.ModuleList()_我是天才很好的博客-程序员秘密

对于CNN前馈神经网络,如果前馈一次写一个forward函数会有些麻烦,在此就有两种简化方式,ModuleList和Sequential。Sequential1 、模型建立方式(1)nn.Sequential()对象.add_module(层名,层class的实例)net1 = nn.Sequential()net1.add_module('conv', nn.Conv2d(3, 3, 3))net1.add_module('batchnorm', nn.BatchNorm2d(3))net1

51单片机应用开发实战手册_Broadview的博客-程序员秘密

<br /><br />华清远见系列图书<br />51单片机应用开发实战手册<br />华清远见嵌入式培训中心  袁东  等编著<br />ISBN 978-7-121-12858-5<br />2011年4月出版<br />定价:59.00元(含DVD光盘1张)<br />16开<br />496页<br />宣传语<br />深入浅出,依靠深厚行业经验讲透技术原理<br />循序渐进,详解典型应用案例提升实战能力<br />内 容 简 介<br />本书通过30个案例的设计过程详细介绍了51单片机开发

只有2~3年左右的开发经验,为什么年薪就可以达到50万+?_小码农 TT的博客-程序员秘密

只有2~3年左右的开发经验,为什么年薪就可以达到50万+?

2021-9-2 Cinemachine 不需要写代码的高级跟随摄像机 2D横板游戏应用_giegie界清流的博客-程序员秘密

Cinemachine在2D横版游戏中的使用方法简介Cinemachine的下载及导入Cinemachine基础设置Cinemachine高级Cinemachine的下载及导入下载现在的版本不再需要从assets store中下载了,直接从package manager中就能找到Cinemachine这个插件。初次找到,请点击Download下载!创建Cinemachine对象我们选择创建虚拟摄像机Virtual Camera后,便会出现一个名为CM vcam1的虚拟摄像机。C.