递归实现指数型枚举(递归)

 写在前面:大家好!我是ACfun,我的昵称来自两个单词Acceptedfun。我是一个热爱ACM的蒟蒻。这篇博客来详解一下递归实现指数型枚举。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正,感谢大家的不吝赐教。我的唯一博客更新地址是:https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油,冲鸭!
用知识改变命运,用知识成就未来!加油 (ง •̀o•́)ง (ง •̀o•́)ง

文章目录题目信息题目描述输入格式输出格式数据范围输入样例输出样例题解解题思路解题代码
原题链接:递归实现指数型枚举

题目信息
题目描述

 从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。

输入格式

 输入一个整数n。

输出格式

 每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案,输出空行。

 本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围

1 ≤ n ≤ 15

输入样例

3

输出样例


3
2
2 3
1
1 3
1 2
1 2 3

题解
解题思路

 我们可以从 1 ~ n 依次考虑每个数选还是不选,我们可以以一个树的形式来描述选还是不选的情况。对于每一种情况有三种状态可以选择:待考虑、选、不选。我们以 0 表示待考虑,1 表示选该位,2 表示不选。比如当 n = 3 的时候,我们画出的递归搜索树如下:
递归实现指数型枚举(递归)
 这其实就是一个 深度优先搜索 的过程,我们先考虑第一位,第一位有两种情况:左子树为不选第一位的情况,右子树为选第一位的情况;当不选第一位时又分成了两种情况,即在不选第一位的情况下第二位不选的情况(左子树)和第二位选的情况(右子树);然后又分成两种情况,选择第三位和不选择第三位。以上是整个左子树的分析情况,即刚开始第一位不选的情况。右子树第一位选择的情况下同理。

 所以我们可以使用 dfs 来递归遍历所有的情况,首先递归遍历不选的情况,然后再递归遍历选择的情况。当每层递归到结束时依次遍历我们记录每个点的状态,如果是 1 我们就输出该数,否则就不输出该数。

解题代码

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 15;

int n;
int s[N]; // 用来记录每个点的状态: 0 表示待考虑,1 表示选择该数, 2 表示不选

void dfs(int x) {
if (x == n) {
for (int i = 0; i <= n; i++) {
if (s[i] == 1) {
printf("%d ", i + 1);
}
}
printf("\n");
return;
}

s[x] = 2;
dfs(x + 1); // 第一个分支,不选
s[x] = 0; // 恢复现场

s[x] = 1;
dfs(x + 1); // 第二个分支,选
s[x] = 0;
}

int main() {
cin >> n;
dfs(0); // 从第一个开始遍历
return 0;
}

我是ACfun,感谢大家的支持!
递归实现指数型枚举(递归)

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

递归实现指数型枚举(递归)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 递归实现指数型枚举(递归)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏