个人主页：仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客
专题分栏：算法_仍有未知等待探索的博客-CSDN博客
目录
一、前言
二、递归指数型枚举
1、题目信息
题目描述
输入格式
输出格式
样例
提示
2、解析
3、代码
一、前言
之前进行枚举的时候，都是进行暴力枚举的策略，将所用可能性都枚举一遍以获得最优解，但是枚举全部元素的效率如同愚公移山，无法应付数据范围稍大的情形。其算法的主要策略是跳过一些无效状态，降低问题的规模。
二、递归指数型枚举
1、题目信息
题目链接：U127142 指数型枚举 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
样例
样例输入
“`
3
“`样例输出
“`
1 2 3
1 2
1 3
1
2 3
2
3
“`提示
1≤n≤15
2、解析
如下图是整个程序的思路，n=3，代表要求 n = 3 的方案数。首先我们要先选第一个数，用一个数组进行存储这位数到底选还是不选。如果选的话，就接着往下一位数进行继续判断，知道要判断的位数大于n，代表结束。然后开始进行回溯。
下图我只对前一半的运行步骤进行了标号，另一半和这个一样。
3、代码
#include#includeusing namespace std;const int N = 20;int n;//枚举的位数int st[N];//存储枚举的位数的信息（某位数是否进行了选择）void bfs(int x){//如果x>n的话，说明枚举选择结束，接着就是输出所选的组合if(x>n){//选n位数，所以循环n次for(int i=1;i>n;bfs(1);return 0;}
谢谢大家的支持！