递归 核心是找一个顺序 保证 不重复的将其遍历完
平常 可以写递归搜索树进行分析
递归实现指数型枚举 acwing 92
https://www.acwing.com/problem/content/description/94/
题目
从 1∼n这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
1 2 3 ........ n
每个数 选和不选 都有两种情况 2 的n次方 * n 的方案
顺序 从 1---n 依次考虑 每个数 选 或者 不选
用一个 st[]数组来记录状态
还要恢复现场 不然影响后续递归
画 递归搜索树
图示
自己模拟图示
#include<iostream>
#include<cstdio>
using namespace std;
const int N= 16;
int st[N];//状态 记录每个位置当前的状态 0 表示还没有考虑 1 表示 选它 2 表示 不选它
int n;
void dfs(int u)
{
//边界
if(u > n)
{
for(int i = 1;i<=n;i++)
{
if(st[i] == 1) printf("%d ",i);
}
printf("\n");
return;
}
st[u] = 2;//不选第一个分支
dfs(u+1);
st[u] = 0;//恢复现场
st[u] = 1;//选第二个分支
dfs(u+1);
st[u] = 0;//恢复现场
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}
递归实现排列型枚举 awcing 94
https://www.acwing.com/problem/content/description/96/
**全排列**
时间复杂度 分析
n的阶乘 * n
见图
**题目**
把 1∼n 这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
对于 字典序而言 从1 开始 自然就是最小的
顺序
1.依次枚举 每个数 放到哪个位置
2.依次枚举 每个位置 放哪个数
代码为第二种思路
图示 递归搜索树
图示 手动模拟
#include<iostream>
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;
}
递归实现组合型枚举 awcing 93
https://www.acwing.com/problem/content/95/
**题目**
从 1∼n这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
**顺序**
从前往后 依次 枚举 每个位置上的数 是 几
组合型枚举（无顺序）
所以 要避免重复
例如 123 132 213 231 321 312 这种情况
方法：手动加一个限制 让其 从小到大排序 或者从大到小排序
是 局部的 只需要让新加的数 大于 前一个数 就行
图示递归搜索数
图示 手动模拟
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 30;
int n,m;//从1---n个 数 中 选出 m 个
int ways[N];//该数组用于放三个位置的数
void dfs(int u,int start)//u 表示枚举哪个位置 start 表示 从哪个数开始枚举
{
//这样写的话 第一个位置 会遍历 4 和 5 但是 这俩种情况是不可能的
//dfs 有个性质 剪枝
if(u+n - start < m) return;
/*
正在选 第 u个 数 说明已经选好 u- 1 个
u- 1 + (n - start + 1) < m;
*/
//边界
if(u > m) //u == m+1
// u == 1 时 一个数还没有选 u = 2 时 选择了一个数 所以说 如果 u == m+1 则说明 选完
{
for(int i = 1;i<=m;i++) printf("%d ",ways[i]);
puts(" ");
return;
}
for(int i = start;i<=n;i++)
{
ways[u] = i;
dfs(u+1,i+1);
//ways[u] = 0;
}
}
int main()
{
scanf("%d%d\n",&n,&m);
dfs(1,1);//第一个位置 第一个数 1 开始枚举
return 0;
}
