目录
⭐什么是dfs
就是深度优先遍历，顾名思义，就是沿着一条路一直走到头，然后再回头
具体方法请看下面的题目
🚥🚥🚥🚥🚥🚥
排列型枚举（全排列）
94. 递归实现排列型枚举 - AcWing题库
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
从一条路遍历到头后，然后再回溯
#include<iostream> using namespace std; const int N=100100; int a[N],b[N]; int n,m; void dfs(int x) { if(x==m+1) { for(int i=1;i<=m;i++) { printf("%d ",a[i]); } return; } for(int i=1;i<=m;i++) { if(b[i]==0) { a[x]=i;//这里是x b[i]=1; dfs(x+1); b[i]=0; } } return; } int main() { cin>>m; dfs(1); }
🚕🚕🚕🚕🚕🚕
排列型枚举（全排列变形）
1537. 递归实现排列类型枚举 II - AcWing题库
给定一个长度为 n 的可包含重复数字的序列，请你求出其所有不重复的全排列。
输入格式
第一行包含整数 n。
第二行包含 n个整数。
输出格式
输出所有的不同排列，每种排列占一行。
在确定每种排列的输出顺序时，第一个数较小的先输出，第一个数相同时，第二个数较小的先输出，以此类推
#include <iostream> #include <algorithm> using namespace std; const int N = 10; int n; int a[N], nums[N]; bool st[N]; void dfs(int u) { if (u == n) { for (int i = 0; i < n; i ++ ) cout << nums[i] << ' '; cout << endl; return; } for (int i = 0; i < n; i ++ ) if (!st[i]) { nums[u] = a[i]; st[i] = true; dfs(u + 1); st[i] = false; //还原现场 while (i + 1 < n && a[i + 1] == a[i]) i ++ ; //跳过重复的 } } int main() { cin >> n; for (int i = 0; i < n; i ++ ) cin >> a[i]; sort(a, a + n); //排序后重复的数字就会排在一起，便于去重 dfs(0); return 0; }
🚕🚕🚕🚕🚕🚕
组合型枚举
93. 递归实现组合型枚举 - AcWing题库
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面
（例如 1 3 5 7 排在 1 3 6 8 前面）。
#include <iostream> using namespace std; int n,m; const int N=100010; int a[N],b[N]; void dfs(int x, int start) { if(x+n-start < m) return; if(x == m+1) { for(int i = 1; i <= m; i++) printf("%d ", a[i]); puts(""); return; } for(int i = start; i <= n; i++)// i从start开始 i<= n { if(b[i]==0) { a[x]=i;//是x b[i]=1; dfs(x+1, i+1); b[i]=0; } } return; } int main() { scanf("%d%d", &n, &m); dfs(1, 1); return 0; }
🚕🚕🚕🚕🚕🚕
指数型枚举
92. 递归实现指数型枚举 - AcWing题库
题目描述
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
#include <iostream> using namespace std; typedef long long ll; int n; int a[20]; bool vis[20]; // 一共tar个坑，当前枚举到第pos个坑 void dfs(int pos, int tar) { if (pos == tar + 1) { for (int i = 1; i <= tar; i ++ ) cout << a[i] << " "; cout << endl; return ; } // 选数填坑 for (int i = 1; i <= n; i ++) { if (!vis[i]) { vis[i] = true; a[pos] = i; dfs (pos + 1, tar); vis[i] = false; } } } int main() { cout << endl; // 不取 cin >> n; for (int i = 1; i <= n; i ++ )//主要是这一步，控制了每次取的数字个数不同 dfs(1, i); return 0; }
🚕🚕🚕🚕🚕🚕
dfs的应用
4868. 数字替换 - AcWing题库
给定两个整数 n,x。
你可以对 x 进行任意次以下操作：
选择 x 的一位数字 y，将 x 替换为 x*y。
请你计算通过使用上述操作，将 x变为一个 n 位数字（不含前导 0），所需要的最少操作次数。
例如，当 n=3,x=2时，对 2 进行如下 4 次操作，即可使其变为 3 位数字：
将 2 替换为 2×2=4。
将 4 替换为 4×4=16。
将 16 替换为 16×6=96。
将 96 替换为 96×9=864。
输入格式
共一行，包含两个整数 n,x。
输出格式
一个整数，表示将 x 变为一个 n 位数字，所需要的最少操作次数。
如果无解，则输出 -1。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int INF = 1000; int n; int ans = INF; void dfs(LL x, int d) { bool st[10] = {0}; int cnt = 0; for (LL y = x; y; y /= 10) { cnt ++ ; st[y % 10] = true;//把不同位数分开 } if (d + n - cnt >= ans) return;//如果当前位数+结果要求的位数-当前的位数>=结果，不成立，结束运行 if (cnt == n) { ans = d; return; } for (int i = 9; i >= 2; i -- ) if (st[i])//如果存在这个位数 dfs(x * i, d + 1); } int main() { LL x; cin >> n >> x; dfs(x, 0); if (ans == INF) ans = -1; cout << ans << endl; return 0; }
🚕🚕🚕🚕🚕🚕
Code over!
