目录
一、基础DFS：递归实现、状态标记、回溯
全排列问题
#include <iostream>
using namespace std;
int n;
int a[15];
bool vis[15];
void dfs(int x)
{
if (x > n)
{
for (int i = 1; i <= n; i++)
{
printf("%5d", a[i]);
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
vis[i] = true;
a[x] = i;
dfs(x + 1);
vis[i] = false;
a[x] = 0;
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}组合问题
#include <iostream>
using namespace std;
int n, r;
int a[30];
void dfs(int x, int start)
{
if (x > r)
{
for (int i = 1; i <= r; i++)
{
printf("%3d", a[i]);
}
cout << endl;
return;
}
for (int i = start; i <= n; i++)
{
a[x] = i;
dfs(x + 1, i + 1);
a[x] = 0;
}
}
int main()
{
cin >> n >> r;
dfs(1, 1);
return 0;
}子集问题
#include <iostream>
using namespace std;
int n;
int a[20];
void dfs(int x)
{
if (x > n)
{
for (int i = 1; i <= n; i++)
{
if (a[i] == 1)
{
cout << i << " ";
}
}
cout << endl;
return;
}
for (int i = 1; i <= 2; i++)
{
a[x] = i;
dfs(x + 1);
a[x] = 0;
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}二、网格DFS：二维矩阵遍历、连通块计数、方向数组
岛屿数量
单词搜索
被围绕的区域
三、 记忆化DFS：动态规划+DFS，缓存中间结果
斐波那契数列（记忆化版）
滑雪
不同路径（带障碍）
四、 剪枝优化：可行性剪枝、最优性剪枝、预处理优化
N 皇后
数独求解
火柴拼正方形
五、树/图的DFS：前序/中序/后序遍历、路径搜索、回溯
二叉树路径和
二叉搜索树的范围和
图中所有路径
六、状态压缩DFS：用二进制表示状态，减少存储开销
翻转游戏
数独
最短哈密尔顿路径
七、综合难题：DFS+贪心、DFS+二分、DFS+并查集
栅栏问题
黄金图形
切断圆环链
