DFS基础与回溯
回溯法简介
回溯法一般使用DFS（深度优先搜索）实现，DFS是一种遍历或搜索图，树或图像等数据结构的算法。上述数据结构不保存下来就是回溯法。
常见的是搜索树，排列型搜索树（节点数一般为n!）与子集型搜索树（节点数一般为2n）。
DFS从起始点开始，沿着一条路尽可能深入，直到无法继续回溯到上一节点为止，继续搜索，直到遍历完整个树或图。DFS使用栈与递归管理节点，一般使用递归。
排列树
graph TB
A((A))
B1((B1))
C1((C1))
B2((B2))
C2((C2))
A-->B1
A-->B2
B1-->C1
B2-->C2
子集树
graph TB
A((A))
B1((B1))
C1((C1))
C2((C2))
B2((B2))
D1((D1))
D2((D2))
A-->B1
A-->B2
B1-->C1
B1-->C2
B2-->D1
B2-->D2
2n(n=2)即4种方案。
回溯法模板
//求1~n的全排列
int a[N];
bool vis[N];//表示数字i（或某个元素）是否使用过
void dfs(int dep) {
//当dep深度等于n+1时说明n层都已经算完了，直接输出结果
if (dep == n + 1) {
for (int i = 1; i <= n; i++)cout << a[i] << ' ';
cout << '\n';
return;
}
//以上为递归出口
//向下搜索，枚举范围
for (int i = 1; i <= n; i++) {
//排除不合法路径，如果i使用过了了就不能用了
if (vis[i])continue;
//修改状态，我们选上了，i现在已经被我们用了
vis[i] = true;
a[dep] = i;
//向下一层递归，形成一个搜索树
dfs(dep + 1);
//恢复现场，只有恢复了现场我们才能不受干扰地向下一个分支进行递归
vis[i] = false;
}
}
例题
N皇后问题
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 15;
int n, ans;
int vis[N][N];//表示被多少个皇后占用了，等于0表示可以放皇后
void dfs(int dep) {
if (dep == n + 1) {
ans++;
return;//递归出口
}
//遍历棋盘上的这一层
for (int i = 1; i <= n; i++) {
if (vis[dep][i])continue;//不为0，这个位置不能放，找下一个位置
//修改状态
for (int _i = 1; _i <= n; ++_i)vis[_i][i]++;//列加1，因为我们是一行行枚举的，所以行可以不用加1
//四个方向的米字，_i是横轴，_j是纵轴
for (int _i = dep, _j = i; _i >= 1 && _j >= 1; --_i, --_j)vis[_i][_j]++;
for (int _i = dep, _j = i; _i <= n && _j >= 1; ++_i, --_j)vis[_i][_j]++;
for (int _i = dep, _j = i; _i >= 1 && _j <= n; --_i, ++_j)vis[_i][_j]++;
for (int _i = dep, _j = i; _i <= n && _j <= n; ++_i, ++_j)vis[_i][_j]++;
dfs(dep + 1);//向下一层递归，一直递归到递归出口，答案加一，退出递归，准备恢复现场（会形成一个树形结构）
//恢复现场，准备下一次搜索
for (int _i = 1; _i <= n; ++_i)vis[_i][i]--;
for (int _i = dep, _j = i; _i >= 1 && _j >= 1; --_i, --_j)vis[_i][_j]--;
for (int _i = dep, _j = i; _i <= n && _j >= 1; ++_i, --_j)vis[_i][_j]--;
for (int _i = dep, _j = i; _i >= 1 && _j <= n; --_i, ++_j)vis[_i][_j]--;
for (int _i = dep, _j = i; _i <= n && _j <= n; ++_i, ++_j)vis[_i][_j]--;
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//每一层必定只有一个皇后，可通过枚举每一层皇后的位置来搜索所有可能解
//层数到n+1时表示找到了一个可行解，不可行的解都到不了n+1层
cin >> n;
dfs(1);
cout << ans << '\n';
return 0;
}