CS-Notes Leetcode 题解精讲：BFS、DFS 与回溯三大搜索算法的完整实现

本篇基于 CS-Notes 的 [Leetcode 题解 - 搜索](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 搜索.md?utm_source=gitcode_repo_files) 展开，系统梳理广度优先搜索（BFS）、深度优先搜索（DFS）与回溯（Backtracking）三类搜索算法的核心思想、程序实现要点与 23 道经典题目的完整 Java 题解。读完本篇后，你将掌握：BFS 分层遍历求解无权图最短路径的正确姿势、DFS 求解连通分量与可达性问题的递归模板，以及回溯法中“选择—递归—撤销”的通用框架与去重、剪枝技巧，可以直接作为面试前搜索类题目的复习手册。

本文档是 [Leetcode 题解 - 目录](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 目录.md?utm_source=gitcode_repo_files) 中“算法思想”板块的搜索部分，与双指针、排序、贪心、二分查找、分治、动态规划等章节并列，题目均选自 Leetcode 中面试高频题，代码以 Java 编写，题解均给出可直接运行的完整实现。

一、广度优先搜索 BFS

广度优先搜索一层一层地进行遍历，每层遍历都是以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。

以 BFS 示意图中的无向图为例，遍历过程如下：

第一层：

• 0 -> {6,2,1,5}

第二层：

• 6 -> {4}
• 2 -> {}
• 1 -> {}
• 5 -> {3}

第三层：

• 4 -> {}
• 3 -> {}

每一层遍历的节点都与根节点距离相同。设 d_i 表示第 i 个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 d_i <= d_j。利用这个结论，可以求解最短路径等最优解问题：第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为 1。

在程序实现 BFS 时需要考虑以下问题：

• 队列：用来存储每一轮遍历得到的节点；
• 标记：对于遍历过的节点，应该将它标记，防止重复遍历。

下面三道题分别展示了 BFS 在网格、整数域和字符串域上的三种典型应用。

1. 网格中的最短路径（1091. Shortest Path in Binary Matrix，Medium）

题目描述：网格中 0 表示可以经过某个位置，求解从左上角到右下角的最短路径长度。例如输入：

[[1,1,0,1],
 [1,0,1,0],
 [1,1,1,1],
 [1,0,1,1]]

这是一道典型的“无权图最短路径”问题：把每个格子看作节点，八方向相邻可走格子之间连边，从 (0,0) 到 (m-1,n-1) 的最短路径长度恰好是 BFS 第一次触达终点时的层数。

public int shortestPathBinaryMatrix(int[][] grids) {
    if (grids == null || grids.length == 0 || grids[0].length == 0) {
        return -1;
    }
    int[][] direction = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
    int m = grids.length, n = grids[0].length;
    Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
    queue.add(new Pair<>(0, 0));
    int pathLength = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        pathLength++;
        while (size-- > 0) {
            Pair<Integer, Integer> cur = queue.poll();
            int cr = cur.getKey(), cc = cur.getValue();
            if (grids[cr][cc] == 1) {
                continue;
            }
            if (cr == m - 1 && cc == n - 1) {
                return pathLength;
            }
            grids[cr][cc] = 1; // 标记
            for (int[] d : direction) {
                int nr = cr + d[0], nc = cc + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                    continue;
                }
                queue.add(new Pair<>(nr, nc));
            }
        }
    }
    return -1;
}

实现要点：

• 分层遍历：每轮先取出当前队列的 size 个节点（pathLength++），再统一入队下一层节点，保证出队即按层计距；
• 原地标记：直接利用 grids[cr][cc] = 1 把走过的可走格子改写成障碍，省去额外的 visited 数组，这是网格题常用的标记技巧；
• 八方向扩展：与后文 DFS 网格题的上下左右四方向不同，本题对角线也可走，所以 direction 是 8 个方向向量；
• 提前终止：第一次从队列中弹出终点时返回的 pathLength 就是最短路径长度，因为 BFS 保证了该层数最小。

2. 组成整数的最小平方数数量（279. Perfect Squares，Medium）

例如给定 n = 12，返回 3，因为 12 = 4 + 4 + 4；给定 n = 13，返回 2，因为 13 = 4 + 9。

这道题的关键是问题建模：将每个整数看成图中的一个节点，如果两个整数之差为一个平方数，那么这两个整数所在的节点就有一条边。要求解最小的平方数数量，就是求解从节点 n 到节点 0 的最短路径。注意本题也可以用动态规划求解，在 [Leetcode 题解 - 动态规划](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 动态规划.md?utm_source=gitcode_repo_files) 部分会再次出现。

public int numSquares(int n) {
    List<Integer> squares = generateSquares(n);
    Queue<Integer> queue = new LinkedList<>();
    boolean[] marked = new boolean[n + 1];
    queue.add(n);
    marked[n] = true;
    int level = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        level++;
        while (size-- > 0) {
            int cur = queue.poll();
            for (int s : squares) {
                int next = cur - s;
                if (next < 0) {
                    break;
                }
                if (next == 0) {
                    return level;
                }
                if (marked[next]) {
                    continue;
                }
                marked[next] = true;
                queue.add(next);
            }
        }
    }
    return n;
}

/**
 * 生成小于 n 的平方数序列
 * @return 1,4,9,...
 */
private List<Integer> generateSquares(int n) {
    List<Integer> squares = new ArrayList<>();
    int square = 1;
    int diff = 3;
    while (square <= n) {
        squares.add(square);
        square += diff;
        diff += 2;
    }
    return squares;
}

实现要点：

• 平方数序列的生成：generateSquares 利用了相邻平方数之差为连续奇数（1、3、5、7…）的规律，通过 square += diff; diff += 2; 递推生成 1、4、9、…，避免了对每个数开平方取整；
• 边界的提前剪枝：由于 squares 是升序的，next < 0 时直接 break 而不是 continue，后面的平方数只会更大；
• 标记数组：marked 数组与队列配合，保证每个整数最多入队一次，因此整体规模受限于整数域 [0, n]。

3. 最短单词路径（127. Word Ladder，Medium）

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

题目描述：找出一条从 beginWord 到 endWord 的最短路径，每次移动规定为改变一个字符，并且改变之后的字符串必须在 wordList 中。

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    wordList.add(beginWord);
    int N = wordList.size();
    int start = N - 1;
    int end = 0;
    while (end < N && !wordList.get(end).equals(endWord)) {
        end++;
    }
    if (end == N) {
        return 0;
    }
    List<Integer>[] graphic = buildGraphic(wordList);
    return getShortestPath(graphic, start, end);
}

private List<Integer>[] buildGraphic(List<String> wordList) {
    int N = wordList.size();
    List<Integer>[] graphic = new List[N];
    for (int i = 0; i < N; i++) {
        graphic[i] = new ArrayList<>();
        for (int j = 0; j < N; j++) {
            if (isConnect(wordList.get(i), wordList.get(j))) {
                graphic[i].add(j);
            }
        }
    }
    return graphic;
}

private boolean isConnect(String s1, String s2) {
    int diffCnt = 0;
    for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            diffCnt++;
        }
    }
    return diffCnt == 1;
}

private int getShortestPath(List<Integer>[] graphic, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] marked = new boolean[graphic.length];
    queue.add(start);
    marked[start] = true;
    int path = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        path++;
        while (size-- > 0) {
            int cur = queue.poll();
            for (int next : graphic[cur]) {
                if (next == end) {
                    return path;
                }
                if (marked[next]) {
                    continue;
                }
                marked[next] = true;
                queue.add(next);
            }
        }
    }
    return 0;
}

实现要点：

• 建图：buildGraphic 用邻接表表示法为词表中每对“相差恰好一个字符”的单词连边。isConnect 在字符差异数超过 1 时通过 diffCnt <= 1 提前终止比较，属于细节上的剪枝；
• 注意返回值语义：本题要求的是路径上单词的个数（含 beginWord 和 endWord），所以 path 从 1 开始计数，触达 end 时直接返回；若 endWord 不在词表中返回 0；
• 建图阶段是 O(N² · L)（N 为词表规模、L 为单词长度），建图后 BFS 是标准的无权图最短路。当词表很大时，还可以考虑不显式建图、在 BFS 过程中即时枚举邻居，或对 beginWord 和 endWord 同时出发的双向 BFS 来降低搜索空间。

二、深度优先搜索 DFS

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。

而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种可达性问题。

在程序实现 DFS 时需要考虑以下问题：

• 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈；
• 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

下面五道题覆盖了 DFS 最典型的四类应用场景：求连通块规模、求连通分量数、基于邻接矩阵的可达性、边界逆向搜索与多方向可达域求交。

1. 查找最大的连通面积（695. Max Area of Island，Medium）

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int maxAreaOfIsland(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }
    m = grid.length;
    n = grid[0].length;
    int maxArea = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            maxArea = Math.max(maxArea, dfs(grid, i, j));
        }
    }
    return maxArea;
}

private int dfs(int[][] grid, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
        return 0;
    }
    grid[r][c] = 0;
    int area = 1;
    for (int[] d : direction) {
        area += dfs(grid, r + d[0], c + d[1]);
    }
    return area;
}

实现要点：把“从某个陆地格子出发能连通到的陆地格子总数”定义成递归返回值，递归中先把自己置 0（grid[r][c] = 0）完成标记，再把四个方向的面积累加进来。外层双重循环负责枚举每一座岛的入口，dfs 对水域返回 0，所以无需判断起点是否为陆地。这是“DFS 计算连通块大小”的标准模板，后文的岛屿数量统计正是它的变体。

2. 矩阵中的连通分量数目（200. Number of Islands，Medium）

Input:
11000
11000
00100
00011

Output: 3

可以将矩阵表示看成一张有向图。

private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }
    m = grid.length;
    n = grid[0].length;
    int islandsNum = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != '0') {
                dfs(grid, i, j);
                islandsNum++;
            }
        }
    }
    return islandsNum;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
        return;
    }
    grid[i][j] = '0';
    for (int[] d : direction) {
        dfs(grid, i + d[0], j + d[1]);
    }
}

实现要点：与上一题的“逐格求面积”不同，本题只需数连通分量的个数。技巧在于：每次在外层循环遇到未访问的陆地时，先用 DFS 把整座岛整体标记成 '0'，然后计数加一。因为标记完成后这座岛上的格子不会再被外层循环触发，所以计数不会重复。从源码结构看，dfs 的返回值类型是 void，说明本题只关心可达性而不关心规模，这正是 DFS 求解可达性问题的典型形态。

3. 好友关系的连通分量数目（547. Friend Circles，Medium）

Input:
[[1,1,0],
 [1,1,0],
 [0,0,1]]

Output: 2

Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

题目描述：好友关系可以看成是一个无向图，例如第 0 个人与第 1 个人是好友，那么 M[0][1] 和 M[1][0] 的值都为 1。

private int n;

public int findCircleNum(int[][] M) {
    n = M.length;
    int circleNum = 0;
    boolean[] hasVisited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!hasVisited[i]) {
            dfs(M, i, hasVisited);
            circleNum++;
        }
    }
    return circleNum;
}

private void dfs(int[][] M, int i, boolean[] hasVisited) {
    hasVisited[i] = true;
    for (int k = 0; k < n; k++) {
        if (M[i][k] == 1 && !hasVisited[k]) {
            dfs(M, k, hasVisited);
        }
    }
}

实现要点：前两题的输入是网格，标记可以直接原地修改；本题输入是邻接矩阵 M，不能破坏原始数据，因此引入独立的 hasVisited 布尔数组标记。递归函数接收当前学生编号 i，遍历同一行的所有列 k，凡是 M[i][k] == 1 且未访问的好友都递归展开。外层同样采用“未访问则 DFS 并计数”的框架——三道题的解题骨架完全一致，区别只在图的表示方式（网格 vs 邻接矩阵）与标记手段（原地改写 vs 独立数组）。

4. 填充封闭区域（130. Surrounded Regions，Medium）

For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

题目描述：使被 'X' 包围的 'O' 转换为 'X'。

解题思路是逆向搜索：被包围的 'O' 难以直接从内部判断，但所有不被包围的 'O' 都一定与棋盘边界连通。因此先填充最外侧，剩下的就是里侧了。

private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int m, n;

public void solve(char[][] board) {
    if (board == null || board.length == 0) {
        return;
    }

    m = board.length;
    n = board[0].length;

    for (int i = 0; i < m; i++) {
        dfs(board, i, 0);
        dfs(board, i, n - 1);
    }
    for (int i = 0; i < n; i++) {
        dfs(board, 0, i);
        dfs(board, m - 1, i);
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'T') {
                board[i][j] = 'O';
            } else if (board[i][j] == 'O') {
                board[i][j] = 'X';
            }
        }
    }
}

private void dfs(char[][] board, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
        return;
    }
    board[r][c] = 'T';
    for (int[] d : direction) {
        dfs(board, r + d[0], c + d[1]);
    }
}

实现要点：

• 三态棋盘：DFS 只从四条边界出发，把边界连通的所有 'O' 临时改写成标记字符 'T'，以此区分“可达边界的安全 O”与“被包围的 O”；
• 收尾转换：标记阶段结束后做一次全局扫描，'T' 还原为 'O'，仍然为 'O' 的（即被完全包围的）转换为 'X'；
• 这里引入第三个字符 'T' 的原因在于题目要求原地修改且只允许 'X'、'O' 两种最终状态，无法像前几题那样用 0/'0' 充当“已访问”。

5. 能到达的太平洋和大西洋的区域（417. Pacific Atlantic Water Flow，Medium）

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

左边和上边是太平洋，右边和下边是大西洋，内部的数字代表海拔，海拔高的地方的水能够流到低的地方，求解水能够流到太平洋和大西洋的所有位置。

private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public List<List<Integer>> pacificAtlantic(int[][] matrix) {
    List<List<Integer>> ret = new ArrayList<>();
    if (matrix == null || matrix.length == 0) {
        return ret;
    }

    m = matrix.length;
    n = matrix[0].length;
    this.matrix = matrix;
    boolean[][] canReachP = new boolean[m][n];
    boolean[][] canReachA = new boolean[m][n];

    for (int i = 0; i < m; i++) {
        dfs(i, 0, canReachP);
        dfs(i, n - 1, canReachA);
    }
    for (int i = 0; i < n; i++) {
        dfs(0, i, canReachP);
        dfs(m - 1, i, canReachA);
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (canReachP[i][j] && canReachA[i][j]) {
                ret.add(Arrays.asList(i, j));
            }
        }
    }

    return ret;
}

private void dfs(int r, int c, boolean[][] canReach) {
    if (canReach[r][c]) {
        return;
    }
    canReach[r][c] = true;
    for (int[] d : direction) {
        int nextR = d[0] + r;
        int nextC = d[1] + c;
        if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
                || matrix[r][c] > matrix[nextR][nextC]) {

            continue;
        }
        dfs(nextR, nextC, canReach);
    }
}

实现要点：

• 逆向思维：题目问“从哪些格子水能流到大海”，如果顺着水流方向（从高到低）对每个格子 DFS，会重复计算且开销巨大。反过来，从大海边界出发，沿着“水能流进来的方向”（即从低海拔流向高海拔）做 DFS，一次遍历即可求出每个海洋的可达域；
• 双可达域求交：canReachP 和 canReachA 分别记录能流到太平洋、大西洋的区域，最终答案就是两个布尔矩阵的交集；
• 方向条件：matrix[r][c] > matrix[nextR][nextC] 时不可达——因为水只能从高处流向低处，从边界反向搜索时只允许走向海拔不低于当前格子的邻居。这道题是“逆向 BFS/DFS + 可达域求交”范式的经典案例。

三、回溯 Backtracking

Backtracking（回溯）属于 DFS。

• 普通 DFS 主要用在可达性问题，这种问题只需要执行到特点的位置然后返回即可。
• 而 Backtracking 主要用于求解排列组合问题，例如有 { 'a','b','c' } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

• 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
• 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

归纳起来，回溯的通用框架是三步：做出选择 → 递归进入下一层 → 撤销选择。与 BFS 的队列和 DFS 的单向标记不同，回溯的标记必须成对出现（置位与复位），否则无法枚举出完整的解空间。下面 15 道题按“基础模板 → 去重 → 剪枝 → 约束求解”的难度递进组织。

1. 数字键盘组合（17. Letter Combinations of a Phone Number，Medium）

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> combinations = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return combinations;
    }
    doCombination(new StringBuilder(), combinations, digits);
    return combinations;
}

private void doCombination(StringBuilder prefix, List<String> combinations, final String digits) {
    if (prefix.length() == digits.length()) {
        combinations.add(prefix.toString());
        return;
    }
    int curDigits = digits.charAt(prefix.length()) - '0';
    String letters = KEYS[curDigits];
    for (char c : letters.toCharArray()) {
        prefix.append(c);                         // 添加
        doCombination(prefix, combinations, digits);
        prefix.deleteCharAt(prefix.length() - 1); // 删除
    }
}

实现要点：这是最纯粹的回溯模板。prefix 的长度隐式表示当前处理到数字串的哪一位（prefix.length() 即下一位的下标），没有显式的 level 参数。核心是 append → 递归 → deleteCharAt 的“选择-撤销”配对：递归返回后必须删掉刚追加的字符，使 prefix 恢复到进入循环前的状态，否则后续分支会携带脏数据。叶子条件是 prefix.length() == digits.length()，即每一位数字都做出了字符选择。

2. IP 地址划分（93. Restore IP Addresses，Medium）

Given "25525511135",
return ["255.255.11.135", "255.255.111.35"].

public List<String> restoreIpAddresses(String s) {
    List<String> addresses = new ArrayList<>();
    StringBuilder tempAddress = new StringBuilder();
    doRestore(0, tempAddress, addresses, s);
    return addresses;
}

private void doRestore(int k, StringBuilder tempAddress, List<String> addresses, String s) {
    if (k == 4 || s.length() == 0) {
        if (k == 4 && s.length() == 0) {
            addresses.add(tempAddress.toString());
        }
        return;
    }
    for (int i = 0; i < s.length() && i <= 2; i++) {
        if (i != 0 && s.charAt(0) == '0') {
            break;
        }
        String part = s.substring(0, i + 1);
        if (Integer.valueOf(part) <= 255) {
            if (tempAddress.length() != 0) {
                part = "." + part;
            }
            tempAddress.append(part);
            doRestore(k + 1, tempAddress, addresses, s.substring(i + 1));
            tempAddress.delete(tempAddress.length() - part.length(), tempAddress.length());
        }
    }
}

实现要点：

• 参数设计：k 记录已经划分的段数，s 是剩余待划分的字符串，每段最多 3 位（i <= 2）；
• 双重合法性检查：一段合法需同时满足“不以 0 开头（除非本身就是 0）”和“数值不超过 255”。i != 0 && s.charAt(0) == '0' 时用 break 而非 continue，因为更长的前缀只会前缀性地包含 0，全部不合法；
• 撤销细节：注意撤销时删除的长度是实际追加的长度——如果该段前拼了分隔符 '.'，part 已经变成 "." + part，tempAddress.delete(...) 以 part.length() 计算，恰好连点带数一起回滚。

3. 在矩阵中寻找字符串（79. Word Search，Medium）

For example,
Given board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

private final static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int m;
private int n;

public boolean exist(char[][] board, String word) {
    if (word == null || word.length() == 0) {
        return true;
    }
    if (board == null || board.length == 0 || board[0].length == 0) {
        return false;
    }

    m = board.length;
    n = board[0].length;
    boolean[][] hasVisited = new boolean[m][n];

    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (backtracking(0, r, c, hasVisited, board, word)) {
                return true;
            }
        }
    }

    return false;
}

private boolean backtracking(int curLen, int r, int c, boolean[][] visited, final char[][] board, final String word) {
    if (curLen == word.length()) {
        return true;
    }
    if (r < 0 || r >= m || c < 0 || c >= n
            || board[r][c] != word.charAt(curLen) || visited[r][c]) {

        return false;
    }

    visited[r][c] = true;

    for (int[] d : direction) {
        if (backtracking(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
            return true;
        }
    }

    visited[r][c] = false;

    return false;
}

实现要点：

• 返回值的复用：与纯枚举型回溯不同，本题只需判断“存在性”，因此 backtracking 的布尔返回值被层层短路——一旦某条路径匹配完整个 word 就立刻 return true 逐层冒泡，外层双重循环也随即终止；
• 标记的撤销位置：visited[r][c] = false 放在四方向循环之后，保证同一次递归链内格子不可复用（防止 ABCB 这种走回头路的假匹配），但不同起点之间的尝试互不影响；
• curLen 表示当前匹配到 word 的第几个字符，与网格坐标 (r, c) 一起构成递归状态。

4. 输出二叉树中所有从根到叶子的路径（257. Binary Tree Paths，Easy）

  1
 /  \
2    3
 \
  5

["1->2->5", "1->3"]

public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();
    if (root == null) {
        return paths;
    }
    List<Integer> values = new ArrayList<>();
    backtracking(root, values, paths);
    return paths;
}

private void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
    if (node == null) {
        return;
    }
    values.add(node.val);
    if (isLeaf(node)) {
        paths.add(buildPath(values));
    } else {
        backtracking(node.left, values, paths);
        backtracking(node.right, values, paths);
    }
    values.remove(values.size() - 1);
}

private boolean isLeaf(TreeNode node) {
    return node.left == null && node.right == null;
}

private String buildPath(List<Integer> values) {
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < values.size(); i++) {
        str.append(values.get(i));
        if (i != values.size() - 1) {
            str.append("->");
        }
    }
    return str.toString();
}

实现要点：values 保存的是当前递归链上的节点值序列，进入节点时 add、离开节点时 remove，天然契合“同一条根到叶路径共享一份中间状态”的需求。叶子判断 isLeaf 要求左右孩子都为空——注意只检查某一侧会漏掉单叉情况。收集答案时用 buildPath 把整条链拼接成 "1->2->5" 格式的字符串。

5. 排列（46. Permutations，Medium）

[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> permutes = new ArrayList<>();
    List<Integer> permuteList = new ArrayList<>();
    boolean[] hasVisited = new boolean[nums.length];
    backtracking(permuteList, permutes, hasVisited, nums);
    return permutes;
}

private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
    if (permuteList.size() == nums.length) {
        permutes.add(new ArrayList<>(permuteList)); // 重新构造一个 List
        return;
    }
    for (int i = 0; i < visited.length; i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        permuteList.add(nums[i]);
        backtracking(permuteList, permutes, visited, nums);
        permuteList.remove(permuteList.size() - 1);
        visited[i] = false;
    }
}

实现要点：排列问题的选择域是“所有尚未使用的元素”，因此每层递归都要从 i = 0 重新扫全数组，用 visited 数组排除已选元素，而不是像组合问题那样从 start 位置向后取。注意收集解时必须 new ArrayList<>(permuteList) 深拷贝——permuteList 是复用中的工作数组，直接存引用会在后续撤销操作中把已收集的解改掉。visited[i] = false 与 remove 成对出现，是排列去“选”的关键。

6. 含有相同元素求排列（47. Permutations II，Medium）

[1,1,2] have the following unique permutations:
[[1,1,2], [1,2,1], [2,1,1]]

数组元素可能含有相同的元素，进行排列时就有可能出现重复的排列，要求重复的排列只返回一个。

在实现上，和 Permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> permutes = new ArrayList<>();
    List<Integer> permuteList = new ArrayList<>();
    Arrays.sort(nums);  // 排序
    boolean[] hasVisited = new boolean[nums.length];
    backtracking(permuteList, permutes, hasVisited, nums);
    return permutes;
}

private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
    if (permuteList.size() == nums.length) {
        permutes.add(new ArrayList<>(permuteList));
        return;
    }

    for (int i = 0; i < visited.length; i++) {
        if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
            continue;  // 防止重复
        }
        if (visited[i]){
            continue;
        }
        visited[i] = true;
        permuteList.add(nums[i]);
        backtracking(permuteList, permutes, visited, nums);
        permuteList.remove(permuteList.size() - 1);
        visited[i] = false;
    }
}

实现要点：排序是去重的前提——只有相同元素相邻，才能用 nums[i] == nums[i - 1] 判断。去重条件 nums[i] == nums[i - 1] && !visited[i - 1] 的含义是：同一层的兄弟分支里，相同的值只允许被选一次。以 [1,1,2] 为例，排序后为 [1,1,2]，若第一个 1 未被选（visited[i-1] 为 false），说明当前正处在同一层的新分支起点，第二个 1 会产出与第一个 1 完全相同的子树，直接剪掉；反之若第一个 1 已在递归链中被选，第二个 1 与它构成“同一层内先后取两个 1”的合法情况，应允许。这是排列类去重的经典写法，后文的组合求和 II、子集 II 均复用同一思想。

7. 组合（77. Combinations，Medium）

If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> combinations = new ArrayList<>();
    List<Integer> combineList = new ArrayList<>();
    backtracking(combineList, combinations, 1, k, n);
    return combinations;
}

private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
    if (k == 0) {
        combinations.add(new ArrayList<>(combineList));
        return;
    }
    for (int i = start; i <= n - k + 1; i++) {  // 剪枝
        combineList.add(i);
        backtracking(combineList, combinations, i + 1, k - 1, n);
        combineList.remove(combineList.size() - 1);
    }
}

实现要点：组合与排列的本质区别是不考虑顺序，因此每层只从 start 向后取数并传入 i + 1，天然保证组合内部递增、不产生重复组合，也不再需要 visited 数组——start 参数本身就是“用过的元素不可再选”的标记。循环上界 n - k + 1 是关键的剪枝：剩余还差 k 个数时，从超过 n - k + 1 的位置开始就没有足够大的数可选了，这部分子树可以整体剪掉。

8. 组合求和（39. Combination Sum，Medium）

given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[[7],[2, 2, 3]]

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> combinations = new ArrayList<>();
    backtracking(new ArrayList<>(), combinations, 0, target, candidates);
    return combinations;
}

private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
                          int start, int target, final int[] candidates) {

    if (target == 0) {
        combinations.add(new ArrayList<>(tempCombination));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            tempCombination.add(candidates[i]);
            backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
            tempCombination.remove(tempCombination.size() - 1);
        }
    }
}

实现要点：与上一题“选满 k 个数”不同，本题的终止条件是 target 归零。注意递归传的起点是 i 而不是 i + 1——因为同一个数可以重复使用，下一层仍可从 candidates[i] 开始选。candidates[i] <= target 是显式剪枝：候选集若有序，超出的数及之后更大的数都可以跳过。本题候选集元素互不相同，故无需去重逻辑。

9. 含有相同元素的组合求和（40. Combination Sum II，Medium）

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> combinations = new ArrayList<>();
    Arrays.sort(candidates);
    backtracking(new ArrayList<>(), combinations, new boolean[candidates.length], 0, target, candidates);
    return combinations;
}

private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
                          boolean[] hasVisited, int start, int target, final int[] candidates) {

    if (target == 0) {
        combinations.add(new ArrayList<>(tempCombination));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (i != 0 && candidates[i] == candidates[i - 1] && !hasVisited[i - 1]) {
            continue;
        }
        if (candidates[i] <= target) {
            tempCombination.add(candidates[i]);
            hasVisited[i] = true;
            backtracking(tempCombination, combinations, hasVisited, i + 1, target - candidates[i], candidates);
            hasVisited[i] = false;
            tempCombination.remove(tempCombination.size() - 1);
        }
    }
}

实现要点：本题同时满足两个约束——每个数字只能用一次（递归传 i + 1，与上一题的 i 形成对照）和元素可能重复（需要去重）。去重逻辑与 Permutations II 完全同构：先 Arrays.sort，再在同层循环中用 candidates[i] == candidates[i - 1] && !hasVisited[i - 1] 跳过重复分支。这里 hasVisited 的语义是“当前递归链中已选”，与排列题中“全局已选”略有差异，但去重判断条件相同。

10. 1-9 数字的组合求和（216. Combination Sum III，Medium）

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

从 1-9 数字中选出 k 个数不重复的数，使得它们的和为 n。

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> combinations = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    backtracking(k, n, 1, path, combinations);
    return combinations;
}

private void backtracking(int k, int n, int start,
                          List<Integer> tempCombination, List<List<Integer>> combinations) {

    if (k == 0 && n == 0) {
        combinations.add(new ArrayList<>(tempCombination));
        return;
    }
    if (k == 0 || n == 0) {
        return;
    }
    for (int i = start; i <= 9; i++) {
        tempCombination.add(i);
        backtracking(k - 1, n - i, i + 1, tempCombination, combinations);
        tempCombination.remove(tempCombination.size() - 1);
    }
}

实现要点：候选集固定为 1~9，且要求不重复取数，因此结构上就是 77. Combinations 的“带目标和”版本：start 保证组合内递增去重，i + 1 保证同一数字不重复取。终止条件需要同时满足 k == 0 && n == 0：只选够 k 个但和不等于 n、或和等于 n 但个数不足，都不是合法解。k == 0 || n == 0 的提前返回是防御性剪枝，例如 n 减到 0 但 k 还没用完时，继续向下只会无效搜索。

11. 子集（78. Subsets，Medium）

找出集合的所有子集，子集不能重复，[1, 2] 和 [2, 1] 这种子集算重复。

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> subsets = new ArrayList<>();
    List<Integer> tempSubset = new ArrayList<>();
    for (int size = 0; size <= nums.length; size++) {
        backtracking(0, tempSubset, subsets, size, nums); // 不同的子集大小
    }
    return subsets;
}

private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets,
                          final int size, final int[] nums) {

    if (tempSubset.size() == size) {
        subsets.add(new ArrayList<>(tempSubset));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        tempSubset.add(nums[i]);
        backtracking(i + 1, tempSubset, subsets, size, nums);
        tempSubset.remove(tempSubset.size() - 1);
    }
}

实现要点：外层按子集规模枚举 size = 0, 1, …, n，对每种规模做一次“选 size 个不重复元素”的回溯，与 77. Combinations 同构（size 即 k）。start 与 i + 1 保证子集内元素按原数组下标递增，从结构上排除了 [1,2] 与 [2,1] 这类重复。空集对应 size = 0 时的 new ArrayList<>(tempSubset)。

12. 含有相同元素求子集（90. Subsets II，Medium）

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> subsets = new ArrayList<>();
    List<Integer> tempSubset = new ArrayList<>();
    boolean[] hasVisited = new boolean[nums.length];
    for (int size = 0; size <= nums.length; size++) {
        backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
    }
    return subsets;
}

private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
                          final int size, final int[] nums) {

    if (tempSubset.size() == size) {
        subsets.add(new ArrayList<>(tempSubset));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
            continue;
        }
        tempSubset.add(nums[i]);
        hasVisited[i] = true;
        backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
        hasVisited[i] = false;
        tempSubset.remove(tempSubset.size() - 1);
    }
}

实现要点：在 78 题模板之上叠加去重：Arrays.sort 使相同值相邻，hasVisited[i] 记录当前递归链中已选元素，nums[i] == nums[i - 1] && !hasVisited[i - 1] 剪掉同层重复分支。以 [1,2,2] 求规模 1 的子集为例：选第一个 2 后递归返回，第二个 2 因前一个 2 已“出链”而被跳过，最终每个值只贡献一份结果；而规模 2 的子集中“两个 2”（[2,2]）是合法的，因为选第二个 2 时第一个 2 仍在递归链内（hasVisited[i-1] 为 true），不会被误剪。

13. 分割字符串使得每个部分都是回文数（131. Palindrome Partitioning，Medium）

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

public List<List<String>> partition(String s) {
    List<List<String>> partitions = new ArrayList<>();
    List<String> tempPartition = new ArrayList<>();
    doPartition(s, partitions, tempPartition);
    return partitions;
}

private void doPartition(String s, List<List<String>> partitions, List<String> tempPartition) {
    if (s.length() == 0) {
        partitions.add(new ArrayList<>(tempPartition));
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        if (isPalindrome(s, 0, i)) {
            tempPartition.add(s.substring(0, i + 1));
            doPartition(s.substring(i + 1), partitions, tempPartition);
            tempPartition.remove(tempPartition.size() - 1);
        }
    }
}

private boolean isPalindrome(String s, int begin, int end) {
    while (begin < end) {
        if (s.charAt(begin++) != s.charAt(end--)) {
            return false;
        }
    }
    return true;
}

实现要点：这是“字符串切分”型回溯：每一层枚举第一个分段的长度 i + 1，用 isPalindrome 双指针对称比较做合法性检查，合法则以剩余子串递归（s.substring(i + 1)），直到剩余串为空收集解。与 IP 划分题的异曲同工之处在于“把问题拆成前缀选择 + 剩余子问题”；区别在于本題没有位数/数值上限，分支完全由回文性决定。从源码结构看，isPalindrome 每次检查都从子串头部开始（begin = 0），因为传入的 s 已经是当前待分割的子串。

14. 数独（37. Sudoku Solver，Hard）

数独是“约束满足问题”的代表：在 9×9 棋盘上填数字，使每行、每列、每个 3×3 宫格内 1~9 各出现一次。回溯求解的关键在于合法性检查的代价——逐格扫描行/列/宫格是 O(21) 的，用标记数组可以把检查降到 O(1)。

private boolean[][] rowsUsed = new boolean[9][10];
private boolean[][] colsUsed = new boolean[9][10];
private boolean[][] cubesUsed = new boolean[9][10];
private char[][] board;

public void solveSudoku(char[][] board) {
    this.board = board;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            int num = board[i][j] - '0';
            rowsUsed[i][num] = true;
            colsUsed[j][num] = true;
            cubesUsed[cubeNum(i, j)][num] = true;
        }
        backtracking(0, 0);
}

private boolean backtracking(int row, int col) {
    while (row < 9 && board[row][col] != '.') {
        row = col == 8 ? row + 1 : row;
        col = col == 8 ? 0 : col + 1;
    }
    if (row == 9) {
        return true;
    }
    for (int num = 1; num <= 9; num++) {
        if (rowsUsed[row][num] || colsUsed[col][num] || cubesUsed[cubeNum(row, col)][num]) {
            continue;
        }
        rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = true;
        board[row][col] = (char) (num + '0');
        if (backtracking(row, col)) {
            return true;
        }
        board[row][col] = '.';
        rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = false;
    }
    return false;
}

private int cubeNum(int i, int j) {
    int r = i / 3;
    int c = j / 3;
    return r * 3 + c;
}

实现要点：

• O(1) 合法性检查：rowsUsed、colsUsed、cubesUsed 三个 9×10 的二维布尔表（第二维 10 是为了方便直接用数字 1~9 做下标）分别记录行、列、宫格中已出现的数字；宫格编号由 cubeNum(i, j) 用整除 (i/3, j/3) 映射到 0~8；
• 初始化预填：solveSudoku 先把棋盘上已有的数字统一登记进三张表，回溯时只需关心空格；
• 自动跳过已填格：backtracking 开头的 while 循环把 (row, col) 推进到下一个空格，行尾回绕到下一行首，row == 9 时说明全盘填满，返回 true；
• 选值-填数-回溯三态联动：填一个数字时同时更新棋盘和三张标记表；子问题失败则成对回滚（恢复 '.' 并清零三个标记），这是约束满足类回溯必须保证的状态一致性。

15. N 皇后（51. N-Queens，Hard）

在 n*n 的矩阵中摆放 n 个皇后，并且每个皇后不能在同一行，同一列，同一对角线上，求所有的 n 皇后的解。

一行一行地摆放，在确定一行中的那个皇后应该摆在哪一列时，需要用三个标记数组来确定某一列是否合法，这三个标记数组分别为：列标记数组、45 度对角线标记数组和 135 度对角线标记数组。

45 度对角线标记数组的长度为 2 * n - 1，通过下图可以明确 (r, c) 的位置所在的数组下标为 r + c。

135 度对角线标记数组的长度也是 2 * n - 1，(r, c) 的位置所在的数组下标为 n - 1 - (r - c)。

private List<List<String>> solutions;
private char[][] nQueens;
private boolean[] colUsed;
private boolean[] diagonals45Used;
private boolean[] diagonals135Used;
private int n;

public List<List<String>> solveNQueens(int n) {
    solutions = new ArrayList<>();
    nQueens = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(nQueens[i], '.');
    }
    colUsed = new boolean[n];
    diagonals45Used = new boolean[2 * n - 1];
    diagonals135Used = new boolean[2 * n - 1];
    this.n = n;
    backtracking(0);
    return solutions;
}

private void backtracking(int row) {
    if (row == n) {
        List<String> list = new ArrayList<>();
        for (char[] chars : nQueens) {
            list.add(new String(chars));
        }
        solutions.add(list);
        return;
    }

    for (int col = 0; col < n; col++) {
        int diagonals45Idx = row + col;
        int diagonals135Idx = n - 1 - (row - col);
        if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]) {
            continue;
        }
        nQueens[row][col] = 'Q';
        colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = true;
        backtracking(row + 1);
        colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = false;
        nQueens[row][col] = '.';
    }
}

实现要点：

• 对角线的下标映射：同一条 45 度对角线上 r + c 为常数，取值范围 0 ~ 2n-2，恰好映射到长度为 2 * n - 1 的数组；135 度对角线上 r - c 为常数，取值范围 -(n-1) ~ (n-1)，加上偏移 n - 1 即得下标 n - 1 - (r - c)。两个映射使冲突检查同样降到 O(1)，与数独的三张标记表是同一思想；
• 按行推进：row 参数即递归层数，每层决定该行皇后的列。由于逐行摆放，行冲突天然不存在，只需检查列与两条对角线；
• 解的收集与状态回滚：row == n 时把棋盘逐行转成字符串列表加入 solutions；每一列尝试后成对恢复 colUsed、两条对角线标记与棋盘字符，保证兄弟分支独立。

四、小结：三大搜索的选型与通用框架

综合上述 23 道题目，可以提炼出以下选型与实现经验：

算法	数据结构	适用问题	典型题目
BFS	队列 + 标记数组	无权图最短路径、最少步数	1091 网格最短路、279 完全平方数、127 单词接龙
DFS	递归栈 + 标记	可达性、连通分量、区域统计	695 岛屿面积、200 岛屿数量、547 好友圈、130 围地、417 太平洋大西洋水流
Backtracking	递归栈 + 成对标记/撤销	排列、组合、子集、字符串分割、约束满足	17 键盘组合、46/47 排列、77/39/40/216 组合与组合求和、78/90 子集、131 回文分割、37 数独、51 N 皇后

几点实现层面的共性结论：

• BFS 求最短路必须配合“按层出队”（记录每层 size）与出队即终止，且只适用于无权图——279 题中“每个平方数边权为 1”的建模正是这一前提；
• DFS 网格题的标记手段有三档：原地改写输入（1091、695、200）、引入独立 visited 数组（547）、引入第三种状态字符（130），选择取决于输入是否可修改与是否需要区分多种状态；
• 回溯框架统一为“选择 → 递归 → 撤销”三步，区别仅在：选择域如何枚举（排列扫全数组 + visited，组合用 start 递推）、合法性约束是什么（IP 段的 255 上限、回文性、数独三约束、皇后三标记）；
• 去重（47、40、90）依赖“排序 + 同层判断”：x[i] == x[i-1] && !visited[i-1]；剪枝（77 的循环上界、39/40 的 target 检查）则把不可能产生解的子树整体裁掉。

以上题解代码均出自 [Leetcode 题解 - 搜索](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 搜索.md?utm_source=gitcode_repo_files)（Java 实现），完整题目导航可参见 [Leetcode 题解 - 目录](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 目录.md?utm_source=gitcode_repo_files)。其中 279. Perfect Squares 在动态规划章节还有另一种解法，可对照阅读 [Leetcode 题解 - 动态规划](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 动态规划.md?utm_source=gitcode_repo_files)，体会“同一问题、不同算法思想”的对比。