本文章原出处：chicago01.top，转载不需说明，随意转载
例题1：递归实现指数型枚举
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
[HTML_REMOVED]
数据范围
1≤n≤15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
题解：
可以很单纯的用STL中的vector枚举就行了，存在两种操作，要或不要。
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> num;
void dfs(int k)
{
//到达枚举边界，输出结果并结束
if(k == n + 1)
{
for(int i = 0;i < num.size();++i)
cout << num[i] << " ";
cout << endl;
return;
}
//不选择这个数
dfs(k+1);
//选择这个数
num.push_back(k);
dfs(k+1);
//回溯
num.pop_back();
}
int main(void)
{
cin >> n;
dfs(1);
return 0;
}
当然也可以向yxc大神学习，用二进制状态压缩。也就是用二进制上的位来记录数有没有被用过。
#include <iostream>
using namespace std;
int n;
// u是当前枚举到的数，state是二进制数记录哪些数被选
void dfs(int u, int state) {
if (u == n) {
for (int i = 0; i < n; i++)
{
//判断第i位是不是1，即有没有被选，如果被选就输出
if (state >> i & 1)
//因为题目是从1开始的，所以要加1
cout << i + 1 << " ";
}
cout << endl;
return ;
}
//不用这个数，不进行操作
dfs (u + 1, state);
//用这个数，把第u位变成1
dfs (u + 1, state | (1 << u));
}
int main(void) {
cin >> n;
dfs(0, 0);
return 0;
}
例2：递归实现组合型枚举
从 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
题解：
其实只需要把例1的代码稍加修改就可以了。再增加两个情况，一种是动态数组所选择的数已经超过了m个，或者剩余的数凑不够m个，排除这两种情况就是我们所要的答案了。
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> num;
void dfs(int k)
{
//如题解所述
if(num.size() > m || num.size() + (n - k + 1) < m)
return;
//到达枚举边界，输出结果并结束
if(k == n + 1)
{
for(int i = 0;i < num.size();++i)
cout << num[i] << " ";
cout << endl;
return;
}
//选择这个数
num.push_back(k);
dfs(k+1);
//回溯
num.pop_back();
//不选择这个数
dfs(k+1);
}
int main(void)
{
cin >> n >> m;
dfs(1);
return 0;
}
例3：递归实现排列型枚举
把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
题解：
这种问题是裸的全排列问题。
我的做法是用一个桶来统计我那些数用过，那些没有用过，然后再用一个数组，把我所用的数加进去，同样的，对于每个数来说，只有两种操作，就是要或不要。
#include<bits/stdc++.h>
using namespace std;
int n;
int num[10];
bool tong[10];
void dfs(int k)
{
if(k == n + 1)
{
for(int i = 1;i <= n;++i)
cout << num[i] << " ";
cout << endl;
return;
}
for(int i = 1;i <= n;++i)
{
if(tong[i] == 0)
{
num[k] = i;
tong[i] = 1;
dfs(k + 1);
num[k] = 0;
tong[i] = 0;
}
}
}
int main(void)
{
cin >> n;
dfs(1);
return 0;
}
棒