DFS 入门题型与模板复习笔记

一、DFS 核心本质

深度优先搜索 = 暴力枚举 + 回溯

• 核心思路：沿着一条路径一直走到底，走不通就退回上一步，换方向继续尝试
• 适用场景：数据规模小（通常 n ≤ 20），求解所有方案数、具体方案、满足条件的最值等
• 关键操作：进入递归前标记状态，递归返回后撤销状态（回溯）

二、四大经典题型 + 标准模板

题型1：网格图路径问题

题型特征

给定 n×m 网格（含障碍物），可向上下左右4个方向移动，常见问法：

• 求起点到终点的路径总数
• 输出任意一条/所有可行路径

核心要素

• 方向数组：控制4个移动方向
• vis 标记数组：防止重复走同一点
• 合法性判断：越界、障碍物、已访问均跳过

标准模板

// 方向数组：上下左右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int n, m, sx, sy, ex, ey;
int a[100][100]; // 地图，1表示障碍
int vis[100][100]; // 访问标记
int ans = 0; // 路径总数

// 参数：当前坐标(x,y)
void dfs(int x, int y) {
    // 1. 终止条件：到达终点
    if (x == ex && y == ey) {
        ans++; // 计数；输出路径题在这里打印
        return;
    }
    // 2. 枚举4个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 3. 合法性判断：不越界、无障碍物、未访问
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m
            && a[nx][ny] != 1 && vis[nx][ny] == 0) {
            // 4. 标记 + 递归下一层
            vis[nx][ny] = 1;
            dfs(nx, ny);
            // 5. 回溯：撤销标记
            vis[nx][ny] = 0;
        }
    }
}

int main() {
    // 读入数据...
    vis[sx][sy] = 1; // 起点必须提前标记！
    dfs(sx, sy);
    cout << ans;
    return 0;
}

题型2：组合枚举问题（选m个，无序）

题型特征

从 n 个元素中选出 m 个，不考虑顺序、不重复选取，常见问法：

• 输出所有组合
• 统计满足条件的组合数量
• 求组合的最值（和、差、乘积等）

核心技巧：用 pre 记录上一个选中的下标，下一个只能从 pre+1 开始，天然保证升序、无重复组合。

标准模板

int n, m;
int a[100]; // 元素数组
int ans = 0;

// step: 已经选了几个元素
// pre: 上一个选中元素的下标
void dfs(int step, int pre) {
    // 1. 终止条件：选满m个
    if (step == m) {
        // 处理答案：输出 / 计数 / 更新最值
        ans++;
        return;
    }
    // 2. 枚举下一个元素，从pre+1开始
    for (int i = pre + 1; i <= n; i++) {
        // 3. 选第i个，递归下一层
        dfs(step + 1, i);
        // 若用全局数组存方案，此处需回溯撤销
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1); // 要求升序输出时必加
    dfs(0, 0); // 初始状态：选了0个，上一个下标为0
    return 0;
}

题型3：全排列问题

题型特征

n 个元素全部参与排列，考虑顺序、每个元素仅用一次，常见问法：

• 输出所有排列
• 按字典序输出排列

标准模板

int n;
int a[100];
int vis[100]; // 标记元素是否被使用

// step: 当前排到第几个位置
void dfs(int step) {
    // 1. 终止条件：排完n个元素
    if (step == n) {
        // 输出当前排列
        return;
    }
    // 2. 枚举每个可用元素
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) { // 元素未被使用
            vis[i] = 1; // 标记为已用
            dfs(step + 1);
            vis[i] = 0; // 回溯：撤销标记
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1); // 字典序输出必备
    dfs(0);
    return 0;
}

题型4：子集枚举（选或不选）

题型特征

每个元素有「选」和「不选」两种选择，枚举所有子集，常见问法：

• 子集和等于目标值的方案数/具体方案
• 子集的最值问题

特点：无需循环枚举，每个元素分两个分支递归。

标准模板

int n, target;
int a[100];
int ans = 0;

// i: 当前处理到第i个元素
// s: 当前子集的和（可替换为其他状态）
void dfs(int i, int s) {
    // 1. 终止条件：所有元素处理完毕
    if (i == n + 1) {
        if (s == target) ans++; // 判断是否满足条件
        return;
    }
    // 2. 分支1：不选第i个元素
    dfs(i + 1, s);
    // 3. 分支2：选第i个元素
    dfs(i + 1, s + a[i]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> target;
    dfs(1, 0); // 从第1个元素开始，当前和为0
    cout << ans;
    return 0;
}

三、DFS 通用解题五步走

1. 定状态：确定 DFS 函数的参数（当前进度 + 当前状态：位置、和、已选数量、上一个下标等）
2. 写终止：到达目标状态时，处理答案并 return
3. 枚举下一步：循环枚举所有可能的选择（方向/元素），或分「选/不选」分支
4. 判合法：过滤越界、重复、障碍等不合法情况
5. 标+递+溯：标记状态 → 递归下一层 → 撤销标记（回溯）

四、高频易错点（避坑必记）

1. 起点漏标记：网格题、排列题的初始状态必须提前标记（如起点 vis 设为1）
2. 回溯不配对：标记和撤销必须成对出现，分别在递归调用的一前一后
3. 组合重复：组合题必须用 pre 递增枚举，不能从1开始，否则会出现重复组合
4. 下标不统一：数组从1开始还是从0开始，全程保持一致，避免越界
5. 终止条件顺序：先判断终止，再做循环扩展，顺序不能写反
6. 变量初始化：计数变量初始化为0，求最小值初始化为极大值（如 1e9）

五、两种传参方式对比

入门阶段推荐先练「全局数组+回溯」，理解回溯本质；怕出错可以用 vector 传值，代码更直观。