DFS

适用场景

枚举所有可能、回溯搜索、连通块统计、路径探索等问题。

核心思想

一条路先走到底，走不通再回退，尝试下一种选择。

完整代码

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> path;
vector<bool> used;

void dfs(int step) {
    if (step == n) {
        for (int x : path) cout << x << " ";
        cout << '\n';
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(i);
            dfs(step + 1);
            path.pop_back();
            used[i] = false;
        }
    }
}

int main() {
    cin >> n;
    used.assign(n + 1, false);
    dfs(0);
    return 0;
}

常见错误

• 没有写递归出口。
• 回溯时忘记撤销标记。
• 递归层数太深导致栈溢出。