递归实现指数型，排列型，组合型枚举
目录
递归实现指数型枚举
题目
从 1∼n1∼n 这 nn 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 nn。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤151≤n≤15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 16;
int n; //代表dfs树得层数
int stu[N]; //状态记录每个位置当前的状态，0表示还没考虑，1表示选它，2表示不选它
void dfs(int u)
{
if(u > n)
{
for(int i = 1;i <= n;i ++)
{
if(stu[i] == 1)
printf("%d ",i);
}
printf("\n");
return;
}
stu[u] = 2;
dfs(u+1);
stu[u] = 0; //恢复现场
stu[u] = 1;
dfs(u+1);
stu[u] = 0;
}
int main()
{
cin>>n;
dfs(1);
return 0;
}解释
按照上面代码开始的时候stu[1] = 2,表示的是不选，就是最左边那条路径，然后dfs[u+1] ，此时u + 1 = 2,相当于在第二层，然后st[2] = 2,表示第二层仍然不选，，再次有dfs[u+1],此时dfs里面u = 3了， 3 > 2,这样在这个dfs嵌套里面，可以打印了，就有由于此时 stu[1] = 2,stu[2] = 2,都不打印，这样，退出这个dfs嵌套,stu[2] = 0, 也就是恢复到了2的位置，然后stu[2] = 1,表示在第二层的时候选择，此时再次遇到dfs，这个dfs里面 u= 3，可以打印，退出之后stu[2] = 0, 退出了之前的嵌套，依次类推即可‘
递归实现排列型枚举
把 1∼n1∼n 这 nn 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 nn。
输出格式
按照从小到大的顺序输出所有方案，每行 11 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤91≤n≤9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路
首先我们遍历每个1~3，如果这个数未被使用，(used[i] ) ，把这个数填进去，再改变其是否调用的状态，在进行dfs函数调用，最后把这个状态恢复原状。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
int state[N]; //0表示没放数，1~n表示放了哪个数
bool used[N]; //true表示用过，false表示还没放过
void dfs(int u)
{
if(u > n)
{
for(int i = 1;i <= n;i ++) printf("%d ",state[i]);
puts("");
return;
}
//依次枚举每个分支，即当前每个数可以填哪些数
for(int i = 1;i <= n;i++)
if(!used[i])
{
state[u] = i;
used[i] = true;
dfs(u+1);
//恢复现场
state[u] = 0;
used[i] = false;
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
} 递归实现组合型枚举
从 1∼n1∼n 这 nn 个整数中随机选出 mm 个，输出所有可能的选择方案。
输入格式
两个整数 n,mn,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 11 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如
1 3 5 7排在1 3 6 8前面）。数据范围
n>0n>0 ,
0≤m≤n0≤m≤n ,
n+(n−m)≤25n+(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 思路
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int n,m;
int way[N];
void dfs(int u, int start)
{
if(u + n - start < m) return; //r如果把后面树都选上，都不够
if(u > m )
{
for(int i = 1;i <=m;i ++) printf("%d ",way[i]);
puts("");
return;
}
for(int i = start ;i <= n;i ++)
{
way[u] = i;
dfs(u+1,i+1);
way[u] = 0; //恢复现场
}
}
int main()
{
scanf("%d%d",&n,&m);
dfs(1,1);
return 0;
}
- 点赞
- 收藏
- 关注作者
评论（0）