递归实现指数型枚举
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int sta[16]; //开状态数组，全局数组，每个函数都能改，dfs函数调用时不用传入
//全局变量，初始值就是0,sta[0]==0
//0--还没考虑，1--选，2--不选
int n; //定义到全局变量，不用传入函数
void dfs(int u) //u是当前位置，
{
if (u>n) //输出过程，u是从1开始，所以结束标志就是u>n
{
for (int i = 1; i <= n; i++)
if (sta[i] == 1)
printf("%d ", i);
puts("");//打印换行
return;
}
sta[u] = 2;//遍历，不选分支，
dfs(u + 1);//递归第一个分支
sta[u] = 0;//恢复现场，
sta[u] = 1;//遍历，选分支，
dfs(u + 1);//递归第二个分支，选分支，
sta[u] = 0;
}
int main()
{
cin >> n;
dfs(1); //从第一位开始（为了方便,数范围就是1~15，和给的数字范围匹配）
}
递归实现排列型枚举
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//顺序：依次枚举每个个位置放哪个数，
//递归树
int n;
int sta[10]; //0表示没放数，1~n表示放了哪个数
int used[10]; //全局变量都为0
void dfs(int u)
{
//step1,输出最后一层，每个坑里的萝卜输出出来
if (u > n) //边界
{
for (int i = 1; i <= n; i++)
cout << sta[i] << " "; //打印方案
puts("");
}
//step2，依次枚举每个分支，即当前位置可以填哪些数，
for (int i = 1; i <= n; i++)
{
if (!used[i])
{
sta[u] = i;
used[i] = 1;
dfs(u + 1);
//恢复现场，有借有还
sta[u] = 0;
used[i] = 0;
}
}
}
int main()
{
cin >> n;
dfs(1); //输入的是位置
}
递归实现组合型枚举
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
//sta[]数组装萝卜，层数u，
//组合，升序组合，不重复，就要设star，就是从哪里开始选
//如i==1选了，那下一位就从star==i+1==2开始
//与全排列不同，不用判是否为空use[]
const int N = 40;
int sta[N];
void dfs(int u, int star)
{
//step1,拔萝卜
if (u > m)
{
for (int i = 1; i <= m; i++)
printf("%d ", sta[i]);
puts("");
return;
}
//step2，递归，dfs
for (int i = star; i <= n; i++)
{
sta[u] = i;
dfs(u + 1, i + 1);
sta[u] = 0; //恢复现场 ，回溯
}
}
int main()
{
cin >> n >> m;
dfs(1, 1);//深度优先搜索，u==1,star==1
}
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 不知细叶谁裁出，二月春风似剪刀
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2022年2月6日23:44:15? ?
|