AcWing 93. 递归实现组合型枚举
2024-09-07 05:28:25
AcWing 93. 递归实现组合型枚举
从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案,每行1个。
首先,同一行内的数升序排列,相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如1 3 5 7排在1 3 6 8前面)。
数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤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
思考题:如果要求使用非递归方法,该怎么做呢?
题解
仍然是递归搜索树,枚举方案为:依次枚举每个位置上的数是几;
本题又用到剪枝来对代码进行了优化,如果发现某方案无解,则可以提前退出。
dfs参数中:
1.表示m个位置,开一个数组存储env[N];
2.loc表示当前枚举到了哪个位置;
3.sma当前最小可以从哪个数枚举 。
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 29;
int n,m;
int env[N];
void dfs(int loc,int sma)//当前枚举到了哪个位置、当前最小可以从哪个数枚举
{
//剪枝
if(loc+n-sma<m) return;//已经选了loc-1个数 假设把sma到n全部选上(n-sma+1)也不够m个数(<m)
if(loc==m+1)//表示枚举结束
{
for(int i=1;i<=m;i++) cout<<env[i]<<' ';
cout<<endl;
return;
}
for(int i=sma;i<=n;i++)
{
env[loc]=i;
dfs(loc+1,i+1);
env[loc]=0;
}
}
int main()
{
cin>>n>>m;
dfs(1,1);//初始从第1个位置开始枚举、最小可以枚举的数为1
return 0;
}
最新文章
- eclipse启动tomcat, http://localhost:8080无法访问
- expect脚本语言用法示例
- 总结ThinkPHP使用技巧经验分享(三)
- WebLogic中的一些基本概念
- Jenkins配置MSBuild编译.net4.6的项目
- servlet中的相对路径和绝对路径 及/, ./, ../的区别
- linux 下解压rar文件
- [Elixir009]像GenServer一样用behaviour来规范接口
- 【HTML5】表单元素
- .net泛型理解
- laravel扩展图片处理Intervention Image
- css布局之三栏布局
- 2014.9.15HTML
- JVM内存最大能调多大分析
- android开发之蓝牙配对连接的方法
- LeetCode——Valid Sudoku
- java中的Volatile 变量
- iphone在iframe页面的宽度不受父页面影响,避免撑开页面
- PHP查看本地文件夹及删除文件夹操作
- React Native 之极光推送jpush-react-native 手把手配置
热门文章
- post请求头的常见类型
- Win10搭建VM12.0.1虚拟机,虚拟机网络同宿主机ping不通的解决办法
- JUnit单元测试%MODULE_WORKING_DIR%&#39; does not exist
- Redis系列(六):数据结构List双向链表LPUSH、LPOP、RPUSH、RPOP、LLEN命令
- js语法基础入门(5.1)
- Python之浅谈绑定方法
- Spring — 循环依赖
- 循环&;&;数组&;&;方法&;&;面向对象
- web前端开发入门全套学习方法路径,兼职在家做网站也能月入上万!
- 如何查看docker run启动参数命令