BFS

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

第一层：

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

第二层：

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

第三层：

4 -> {}
3 -> {}

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

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

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

1. 计算在网格中从原点到特定点的最短路径长度

Leetcode-1091. 二进制矩阵中的最短路径

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。

一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, …, C_k 组成：

相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）

返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。

总结：0 表示可以经过某个位置，求解从左上角到右下角的最短路径长度。

提示：

1 <= grid.length == grid[0].length <= 100
grid[i][j] 为 0 或 1

解法：

Java

用于求最短路径，非常重要

class Solution {
   
    private int[][] directions = {
   {
   -1, 0}, {
   -1, 1}, {
   -1, -1}, {
   0, -1}, {
   0, 1}, {
   1, 0}, {
   1, 1}, {
   1, -1}};
    public int shortestPathBinaryMatrix(int[][] grid) {
   
        int m = grid.length, n = grid[0].length;
        if (grid[0][0]==1 || grid[m-1][n-1]==1) return -1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{
   0,0});
        grid[0][0] = 1;
        int res = 1;
        while (!q.isEmpty()) {
   
            int size = q.size();
            for (int i=0;i<size;i++) {
   
                int[] pos = q.remove();
                if (pos[0]==m-1 && pos[1]==n-1) return res;
                for (int[] d: directions) {
   
                    int nextX = pos[0]+d[0], nextY = pos[1]+d[1];
                    if (nextX>=0 && nextX<m && nextY>=0 && nextY<n && grid[nextX][nextY]==0) {
   
                        q.add(new int[]{
   nextX, nextY});
                        grid[nextX][nextY] = 1;
                    }
                }
            }
            res++;
        }
        return -1;
    }
}

2. 组成整数的最小平方数数量

Leetcode-279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解法：

动态规划

Java

class Solution {
   
    public int numSquares(int n) {
   
        if (n<=1) return n;
        List<Integer> lst = generateSquareList(n);
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i=2;i<=n;i++) {
   
            int min = Integer.MAX_VALUE;
            for (int square:lst) {
   
                if (square <= i) min = Math.min(min, 1+dp[i-square]);
            }
            dp[i] = min;
        }
        return dp[n];
    }
    private List<Integer> generateSquareList(int n) {
   
        List<Integer> lst = new ArrayList<>();
        int diff = 3;
        int square = 1;
        while (square<=n) {
   
            lst.add(square);
            square += diff;
            diff += 2;
        }
        return lst;
    }
}

广度优先搜索

Java

可以将每个整数看成图中的一个节点，如果两个整数之差为一个平方数，那么这两个整数所在的节点就有一条边。

要求解最小的平方数数量，就是求解从节点 n 到节点 0 的最短路径。
marked可以省下很多的时间，如果不使用marked同样可以ac，但是效率慢很多。

class Solution {
   
    public int numSquares(int n) {
   
        List<Integer> lst = generateSquareList(n);
        boolean[] marked = new boolean[n+1];
        marked[n] = true;
        int res = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        while (!q.isEmpty()) {
   
            int size = q.size();
            res++;
            while (size-- > 0) {
   
                int cur = q.remove();
                for (int square: lst) {
   
                    int next = cur - square;
                    if (next<0) break;
                    if (next==0) return res;
                    if (marked[next]) continue;
                    q.add(next);
                    marked[next] = true;
                }
            }
        }
        return n;
    }
    private List<Integer> generateSquareList(int n) {
   
        List<Integer> lst = new ArrayList<>();
        int diff = 3;
        int square = 1;
        while (square<=n) {
   
            lst.add(square);
            square += diff;
            diff += 2;
        }
        return lst;
    }
}

3. 最短单词路径

Leetcode-127. 单词接龙

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

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

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

示例 2:

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

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

解法：

Java

https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode/

class Solution {
   
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
   
        wordList.add(beginWord);
        int n = wordList.size();
        int start = n-1, end = 0;
        while (end<n && !wordList.get(end).equals(endWord)) end++;
        if (end==n) return 0;
        List<Integer>[] simListAry = getSimListAry(wordList);
        return getShortestPath(start, end, simListAry);
    }
    private List<Integer>[] getSimListAry(List<String> wordList) {
   
        int n = wordList.size();
        List<Integer>[] simListAry = new ArrayList[n];
        for (int i=0;i<n;i++) {
   
            simListAry[i] = new ArrayList<>();
            for (int j=0;j<n;j++) {
   
                if (isCorrect(wordList.get(i), wordList.get(j)) && j!=i) simListAry[i].add(j);
            }
        }
        return simListAry;
    }
    private boolean isCorrect(String str1, String str2) {
   
        int count = 0;
        for (int i=0;i<str1.length();i++) {
   
            if (str1.charAt(i)!=str2.charAt(i)) count++;            
        }
        return count==1;
    }
    private int getShortestPath(int start, int end, List<Integer>[] simListAry) {
   
        int res = 1;
        Queue<Integer> q = new LinkedList<>();
        boolean[] marked = new boolean[simListAry.length];
        q.add(start);
        marked[start] = true;
        while (!q.isEmpty()) {
   
            int size = q.size();
            res++;
            while (size-- > 0) {
   
                int idx = q.remove();
                for (int next: simListAry[idx]) {
   
                    if (next==end) return res;
                    if (marked[next]) continue;
                    marked[next] = true;
                    q.add(next);
                }
            }
        }
        return 0;
    }
}

DFS

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

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

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

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

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

1. 查找最大的连通面积

Leetcode-695. 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[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]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

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

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解法：

Java

对于矩阵类型，一定要遍历每个进行backtrack的位置，找到开始backtrack的点
dfs返回int类型案例

class Solution {
   
    private int m, n;
    private int[][] directions = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    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 i, int j) {
   
        if (i<0 || i>=m || j<0 || j>=n || grid[i][j]==0) return 0;
        grid[i][j] = 0;
        int area = 1;
        for (int[] d: directions) {
   
            area += dfs(grid, i+d[0], j+d[1]);
        }
        return area;
    }
}

2. 矩阵中的连通分量数目

Leetcode-200. 岛屿数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

示例 2:

解法：

Java

dfs返回int类型案例

class Solution {
   
    private int m, n;
    private int[][] directions = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    public int numIslands(char[][] grid) {
   
        if (grid==null || grid.length==0) return 0;
        m = grid.length;
        n = grid[0].length;
        int num = 0;
        for (int i=0;i<m;i++) {
   
            for (int j=0;j<n;j++) {
   
                num += dfs(grid, i, j);
            }
        }
        return num;
    }
    private int dfs(char[][] grid, int i, int j) {
   
        if (i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0') return 0;
        grid[i][j] = '0';
        for (int[] d: directions) {
   
            dfs(grid, i+d[0], j+d[1]);
        }
        return 1;
    }
}

class Solution {
   
    private int m, n;
    private int[][] directions = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    public int numIslands(char[][] grid) {
   
        if (grid==null || grid.length==0) return 0;
        m = grid.length;
        n = grid[0].length;
        int num = 0;
        for (int i=0;i<m;i++) {
   
            for (int j=0;j<n;j++) {
   
                if (grid[i][j]=='1') {
   
                    dfs(grid, i, j);
                    num++;
                }
            }
        }
        return num;
    }
    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: directions) {
   
            dfs(grid, i+d[0], j+d[1]);
        }
    }
}

3. 好友关系的连通分量数目

547. 朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

示例 2:

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意：

N 在[1,200]的范围内。
对于所有学生，有M[i][i] = 1。
如果有M[i][j] = 1，则有M[j][i] = 1。

解法：

Java

dfs一般都是返回空值

class Solution {
   
    private int n;
    public int findCircleNum(int[][] M) {
   
        if (M==null || M.length==0) return 0;
        n = M.length;
        int num = 0;
        boolean[] marked = new boolean[n];
        for (int i=0;i<n;i++) {
   
            if (!marked[i]) {
   
                dfs(M, i, marked);
                num++;
            }
        }
        return num;
    }
    private void dfs(int[][] M, int i, boolean[] marked) {
   
        marked[i] = true;
        for (int j=0;j<n;j++) {
   
            if (M[i][j]==1 && !marked[j]) dfs(M, j, marked);
        }
    }
}

4. 填充封闭区域

Leetcode-130. 被围绕的区域

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解法：

Java

dfs返回空值

由于边界上的O是不会被填充的，所以只要和边界上连接的O就都不会被填充，从边界上向内部进行搜索，找到的O都改成*，在进行整体遍历，所有*
都是O，剩余的O就是没有与边界连接的，变成X

class Solution {
   
    private int m, n;
    private int[][] directions = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    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 j=0;j<n;j++) {
   
            dfs(board, 0, j);
            dfs(board, m-1, j);
        }
        for (int i=0;i<m;i++) {
   
            for (int j=0;j<n;j++) {
   
                if (board[i][j] == '*') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
        return;
    }
    private void dfs(char[][]board, int i, int j) {
   
        if (i<0 || i>=m || j<0 || j>=n || board[i][j]!='O') return;
        board[i][j] = '*';
        for (int[] d: directions) {
   
            dfs(board, i+d[0], j+d[1]);
        }
    }
}

5. 能到达的太平洋和大西洋的区域

Leetcode-417. 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要
m 和 n 都小于150

示例：

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

解法：

Java

跟上题类似，dfs的作用就是让能调用到dfs的位置标记为true，用两个boolean数组标记能访问到P和A的位置，都为true则添加到list中

class Solution {
   
    private int m, n;
    private int[][] directions = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
   
        List<List<Integer>> res = new ArrayList<>();
        if (matrix==null || matrix.length==0) return res;
        m = matrix.length;
        n = matrix[0].length;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];
        for (int i=0;i<m;i++) {
   
            dfs(matrix, i, 0, canReachP);
            dfs(matrix, i, n-1, canReachA);
        }
        for (int j=0;j<n;j++) {
   
            dfs(matrix, 0, j, canReachP);
            dfs(matrix, m-1, j, canReachA);
        }
        for (int i=0;i<m;i++) {
   
            for (int j=0;j<n;j++){
   
                if (canReachP[i][j] && canReachA[i][j]) res.add(Arrays.asList(i, j));
            }
        }
        return res;
    }
    private void dfs(int[][] matrix, int i, int j, boolean[][] canReach) {
   
        if (canReach[i][j] || i<0 || i>=m || j<0 || j>=n) return;
        canReach[i][j] = true;
        int r = 0, c = 0;
        for (int[] d: directions) {
   
            r = i+d[0];
            c = j+d[1];
            if ( r<0 || r>=m || c<0 || c>=n ||matrix[i][j] > matrix[r][c]) continue;
            dfs(matrix, r, c, canReach);
        }
    }
}

Backtracking

Backtracking（回溯）属于 DFS。

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

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

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

1. 数字键盘组合

Leetcode-17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解法：

Java

class Solution {
   
    private static final String[] KEYS = {
   "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
   
        List<String> res = new ArrayList<>();
        if (digits==null || digits.length()==0) return res;
        backtracking(new StringBuilder(), digits, res);
        return res;
    }
    private void backtracking(StringBuilder sb, String digits, List<String> res) {
   
        if (sb.length()==digits.length()) {
   
            res.add(sb.toString());
            return;
        }
        int curDigit = digits.charAt(sb.length())-'0';
        String letter = KEYS[curDigit];
        for (char c: letter.toCharArray()) {
   
            sb.append(c);
            backtracking(sb, digits, res);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

2. IP 地址划分

Leetcode-93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

解法：

Java

class Solution {
   
    public List<String> restoreIpAddresses(String s) {
   
        List<String> res = new ArrayList<>();
        backtracking(0, new StringBuilder(), res, s);
        return res;
    }
    private void backtracking(int k, StringBuilder sb, List<String> res, String s) {
   
        // ip总共四部分
        if (k==4 || s.length()==0) {
   
            if (k==4 && s.length()==0) res.add(sb.toString());
            return;
        }
        // 每次长度可以是1-3个字符
        for (int i=0;i<s.length() && i<=2;i++) {
   
            if (s.charAt(0)=='0' && i!=0) break;
            String part = s.substring(0, i+1);
            if (Integer.valueOf(part)<=255) {
   
                if (k!=0) part = "."+part;
                sb.append(part);
                backtracking(k+1, sb, res, s.substring(i+1));
                sb.delete(sb.length()-part.length(), sb.length());
            }
        }
    }
}

3. 在矩阵中寻找字符串

Leetcode-79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

解法：

Java

很重要的案例，backtrack返回boolean类型

class Solution {
   
    private int[][] directions = {
   {
   -1, 0}, {
   1, 0}, {
   0, -1}, {
   0, 1}};
    private int m, 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[][] marked = new boolean[m][n];
        for (int i=0;i<m;i++) {
   
            for (int j=0;j<n;j++) {
   
                if (backtracking(0, i, j, marked, board, word)) return true;
            }
        }
        return false;
    }
    
    private boolean backtracking(int len, int r, int c, boolean[][] marked, final char[][] board, final String word) {
   
        if (len==word.length()) return true;
        if (r<0 || r>=m || c<0 || c>=n || marked[r][c] || board[r][c]!=word.charAt(len)) return false;
        marked[r][c] = true;
        for (int[] d: directions) {
   
            if (backtracking(len+1, r+d[0], c+d[1], marked, board, word)) return true;
        }
        marked[r][c] = false;
        return false;
    }
}

4. 输出二叉树中所有从根到叶子的路径

Leetcode-257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

解法：

Java

树种进行backtrack，很重要的案例

class Solution {
   
    public List<String> binaryTreePaths(TreeNode root) {
   
        List<String> res = new ArrayList<>();
        if (root==null) return res;
        List<Integer> path = new ArrayList<>();
        backtracking(root, path, res);
        return res;
    }
    private void backtracking(TreeNode node, List<Integer> path, List<String> res) {
   
        if (node==null) return;
        path.add(node.val);
        if (node.left==null && node.right==null) res.add(buildPath(path));
        else {
   
            backtracking(node.left, path, res);
            backtracking(node.right, path, res);
        }
        path.remove(path.size()-1);
    }
    private String buildPath(List<Integer> path) {
   
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<path.size();i++) {
   
            sb.append(path.get(i));
            if (i!=path.size()-1) sb.append("->");
        }
        return sb.toString();
    }
}

5. 排列

Leetcode-46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解法：

Java

没有重复值的全排列，需要marked进行判断标记，backtrack内部进行未标记的取值

class Solution {
   
    public List<List<Integer>> permute(int[] nums) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> premuteLst = new ArrayList<>();
        boolean[] marked = new boolean[nums.length];
        backtracking(res, premuteLst, marked, nums);
        return res;
    }
    private void backtracking(List<List<Integer>> res, List<Integer> premuteLst, boolean[] marked, int[] nums) {
   
        if (premuteLst.size() == nums.length) {
   
            res.add(new ArrayList<>(premuteLst)); // 必须重新构造premuteLst，否则添加的都是同一个premuteLst
            return;
        }
        for (int i=0;i<nums.length;i++) {
   
            if (marked[i]) continue;
            marked[i] = true;
            premuteLst.add(nums[i]);
            backtracking(res, premuteLst, marked, nums);
            premuteLst.remove(premuteLst.size()-1);
            marked[i] = false;
        }
    }
}

6. 含有相同元素求排列

Leetcode-47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解法：

Java

升级版，使用判前的方式，一定要先进行sort

在实现上，和 Permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。（相当于前一个元素已经经历过marked[i] = true和marked[i] = false的过程或者已经被跳过，如果前一个元素marked为true，说明正在前一个元素的遍历过程中，应该继续进行）

class Solution {
   
    public List<List<Integer>> permuteUnique(int[] nums) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> premuteLst = new ArrayList<>();
        boolean[] marked = new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(res, premuteLst, marked, nums);
        return res;
    }
    private void backtracking(List<List<Integer>> res, List<Integer> premuteLst, boolean[] marked, final int[] nums) {
   
        if (premuteLst.size() == nums.length) {
   
            res.add(new ArrayList<>(premuteLst));
            return;
        }
        for (int i=0;i<nums.length;i++) {
   
            if (i!=0 && nums[i]==nums[i-1] && !marked[i-1]) continue;
            if (marked[i]) continue;
            marked[i] = true;
            premuteLst.add(nums[i]);
            backtracking(res, premuteLst, marked, nums);
            premuteLst.remove(premuteLst.size()-1);
            marked[i] = false;
        }
    }
}

7. 组合

Leetcode-77. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解法：

Java

这道题跟上面的不同之处在于[1, 2]和[2, 1]是相同的，需要排除掉，如果还按照上题这么写会有大量重复的问题

// 错误答案
class Solution {
   
    public List<List<Integer>> combine(int n, int k) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> combineLst = new ArrayList<>();
        boolean[] marked = new boolean[n+1];
        backtracking(res, combineLst, marked, n, k);
        return res;
    }
    private void backtracking(List<List<Integer>> res, List<Integer> combineLst, boolean[] marked, final int n, final int k) {
   
        if (combineLst.size() == k) {
   
            res.add(new ArrayList<>(combineLst));
            return;
        }
        for (int i=1;i<=n;i++) {
   
            if (marked[i]) continue;
            marked[i] = true;
            combineLst.add(i);
            backtracking(res, combineLst, marked, n, k);
            combineLst.remove(combineLst.size()-1);
            marked[i] = false;
        }
    }
}

所以我们需要更改每次遍历时开始的位置，利用start防止回头，start仍为i表示i位置可以多次使用，为i+1表示只能使用一次。有了start就可以不用marked了，因为不会访问前面的元素了

class Solution {
   
    public List<List<Integer>> combine(int n, int k) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> lst = new ArrayList<>();
        backtracking(res, lst, n, k, 1);
        return res;
    }
    private void backtracking(List<List<Integer>> res, List<Integer> lst, int n, int k, int start) {
   
        if (lst.size() == k) {
   
            res.add(new ArrayList<>(lst));
            return;
        }
        for (int i=start;i<=n;i++) {
   
            lst.add(i);
            backtracking(res, lst, n, k, i+1);
            lst.remove(lst.size()-1);
        }
    }
}

8. 组合求和

Leetcode-39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

解法：

Java

依然还是使用start进行防止回头，否则会有[2, 2, 3]和[2, 3, 2]这种重复例子

class Solution {
   
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> comLst = new ArrayList<>();
        backtracking(candidates, target, 0, res, comLst);
        return res;
    }
    private void backtracking(final int[] candidates, int target, int start, List<List<Integer>> res, List<Integer> comLst) {
   
        if (target==0) {
   
            res.add(new ArrayList<>(comLst));
            return;
        }
        for (int i=start;i<candidates.length;i++) {
   
            if (candidates[i]>target) continue;
            comLst.add(candidates[i]);
            backtracking(candidates, target-candidates[i], i, res, comLst);
            comLst.remove(comLst.size()-1);
        }
    }
}

9. 含有相同元素的组合求和

Leetcode-40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

解法：

Java

class Solution {
   
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> comLst = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] marked = new boolean[candidates.length];
        backtracking(candidates, target, marked, 0, res, comLst);
        return res;
    }
    private void backtracking(final int[] candidates, int target, boolean[] marked, int start, List<List<Integer>> res, List<Integer> comLst) {
   
        if (target==0) {
   
            res.add(new ArrayList<>(comLst));
            return;
        }
        for (int i=start;i<candidates.length;i++) {
   
            if (i!=0 && candidates[i]==candidates[i-1] && !marked[i-1]) continue;
            if (candidates[i]>target) continue;
            marked[i] = true;
            comLst.add(candidates[i]);
            backtracking(candidates, target-candidates[i], marked, i+1, res, comLst);
            comLst.remove(comLst.size()-1);
            marked[i] = false;
        }
    }
}

10. 1-9 数字的组合求和

Leetcode-216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

解法：

Java

class Solution {
   
    public List<List<Integer>> combinationSum3(int k, int n) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> lst = new ArrayList<>();
        backtracking(res, lst, n, k, 1);
        return res;
    }
    private void backtracking(List<List<Integer>> res, List<Integer> lst, int n, int k, int start) {
   
        if (lst.size()==k) {
   
            if (n==0) res.add(new ArrayList<>(lst));
            return;
        }
        for (int i=start;i<=9;i++) {
   
            if (i>n) continue;
            lst.add(i);
            backtracking(res, lst, n-i, k, i+1);
            lst.remove(lst.size()-1);
        }
    }
}

11. 子集

Leetcode-78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解法：

Java

子集不能重复，需要start防止回头

class Solution {
   
    public List<List<Integer>> subsets(int[] nums) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> lst = new ArrayList<>();
        if (nums==null || nums.length==0) return res;
        backtracking(res, lst, nums, 0);
        return res;
    }
    private void backtracking(List<List<Integer>> res, List<Integer> lst, int[] nums, int start) {
   
        res.add(new ArrayList<>(lst));
        for (int i=start; i<nums.length; i++) {
   
            lst.add(nums[i]);
            backtracking(res, lst, nums, i+1);
            lst.remove(lst.size()-1);
        }
    }
}

12. 含有相同元素求子集

Leetcode-90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解法：

Java

与前面的题类似
结果与子集内元素顺序有关（需要去重），元素只能使用一次，使用start，backtrack的时候令start=i+1
元素可以使用无限次，使用start，backtrack的时候令start=i即可
含有重复，并且只能用一次，结果与子集内元素顺序有关（需要去重），使用start+boolean[]，并且backtrack的时候令start=i+1

class Solution {
   
    public List<List<Integer>> subsetsWithDup(int[] nums) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> lst = new ArrayList<>();
        res.add(new ArrayList<>());
        boolean[] marked = new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(res, lst, nums, marked, 0);
        return res;
    }
    private void backtracking(List<List<Integer>> res, List<Integer> lst, int[] nums, boolean[] marked, int start) {
   
        if (start==nums.length || marked[start]) return;
        for (int i=start; i<nums.length; i++) {
   
            if (i!=0 && nums[i]==nums[i-1] && !marked[i-1]) continue;
            if (marked[i]) continue;
            lst.add(nums[i]);
            marked[i] = true;
            res.add(new ArrayList<>(lst));
            backtracking(res, lst, nums, marked, i+1);
            marked[i] = false;
            lst.remove(lst.size()-1);
        }
    }
}

13. 分割字符串使得每个部分都是回文数

Leetcode-131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

解法：

Java

class Solution {
   
    public List<List<String>> partition(String s) {
   
        List<List<String>> res = new ArrayList<>();
        List<String> partitionLst = new ArrayList<>();
        backtracking(s, res, partitionLst);
        return res;
    }
    private void backtracking(String s, List<List<String>> res, List<String> partitionLst) {
   
        if (s.length()==0) {
   
            res.add(new ArrayList<>(partitionLst));
            return;
        }
        for (int i=0;i<s.length();i++) {
   
            if (!isPalindrome(s, 0, i)) continue;
            partitionLst.add(s.substring(0,i+1));
            backtracking(s.substring(i+1), res, partitionLst);
            partitionLst.remove(partitionLst.size()-1);
        }
    }
    private boolean isPalindrome(String s, int begin, int end) {
   
        if (s==null) return false;
        while (begin < end) {
   
            if (s.charAt(begin++) != s.charAt(end--)) return false;
        }
        return true;
    }
}

14. 数独

Leetcode-37. 解数独

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

解法：

Java

如果是for i for j两层循环中遍历各个正方形的位置，使用这样的公式作为board[m][n]中的m、n（对应36题）：

int m = i/3*3 + j/3;
int n = i%3*3 + j%3;

如果是已知位置的i、j左边，想遍历board[i][j]所在的小cube中的所有元素，应该使用这样的m、n（对应37题）：

int m = row/3*3 + i/3;
int n = col/3*3 + i%3;

class Solution {
   
    public void solveSudoku(char[][] board) {
   
        if (board==null || board.length==0 || board[0].length==0) return;
        backtracking(board);
    }
    private boolean backtracking(char[][] board) {
   
        for (int i=0;i<board.length;i++) {
   
            for (int j=0;j<board[0].length;j++) {
   
                if (board[i][j] != '.') continue;
                for (char c='1';c<='9';c++) {
   
                    if (!isValid(board, i, j, c)) continue;
                    board[i][j] = c;
                    if (backtracking(board)) return true;
                    board[i][j] = '.';
                }
                return false; // 没有位置可以填写数字，说明之前填的有错误
            }
        }
        return true; // 所有位置都被填完
    }
    private boolean isValid(char[][] board, int row, int col, char c) {
   
        for (int i=0;i<board.length;i++) {
   
            int m = row/3*3 + i/3;
            int n = col/3*3 + i%3;
            if (board[row][i]==c || board[i][col]==c || board[m][n]==c) return false; // 行、列、cube中都满足
        }
        return true;
    }
}

36题类似，判断有效的数独。

class Solution {
   
    public boolean isValidSudoku(char[][] board) {
   
        return backtracking(board);
    }
    private boolean backtracking(char[][] board) {
   
        for (int i=0; i<board.length; i++) {
   
            for (int j=0; j<board[0].length; j++) {
   
                if (board[i][j] == '.') continue;
                char c = board[i][j];
                board[i][j] = '.';
                if (!isValid(board, i, j, c)) return false;
                board[i][j] = c;
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col, char c) {
   
        for (int i=0; i<board.length; i++) {
   
            int m = row/3*3 + i/3;
            int n = col/3*3 + i%3;
            if (board[row][i]==c || board[i][col]==c || board[m][n]==c) return false;
        }
        return true;
    }
}

15. N 皇后

Leetcode-51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

解法：

Java

左对角线上元素横坐标加纵坐标和相同（注意纵坐标向下增加，左上角为原点）
右对角线上元素横坐标减纵坐标差相同

class Solution {
   
    private int n;
    public List<List<String>> solveNQueens(int n) {
   
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> lst = new ArrayList<>();
        Set<Integer> cols = new HashSet<>();
        Set<Integer> leftDiags = new HashSet<>();
        Set<Integer> rightDiags = new HashSet<>();
        this.n = n;
        backtracking(res, lst, cols, leftDiags, rightDiags, 0);
        return formatting(res);
    }
    private void backtracking(List<List<Integer>> res, List<Integer> lst, Set<Integer> cols, Set<Integer> leftDiags, Set<Integer> rightDiags, int level) {
   
        if (lst.size() == n) {
   
            res.add(new ArrayList<>(lst));
            return;
        }
        for (int i=0; i<n; i++) {
   
            if (cols.contains(i) || leftDiags.contains(i+level) || rightDiags.contains(i-level)) continue;
            lst.add(i);
            cols.add(i);
            leftDiags.add(i+level);
            rightDiags.add(i-level);
            backtracking(res, lst, cols, leftDiags, rightDiags, level+1);
            rightDiags.remove(i-level);
            leftDiags.remove(i+level);
            cols.remove(i);
            lst.remove(lst.size()-1);
        }
    }
    private List<List<String>> formatting(List<List<Integer>> lst) {
   
        List<List<String>> res = new ArrayList<>();
        for (List<Integer> l: lst) {
   
            List<String> strlst = new ArrayList<>();
            for (int idx: l) {
   
                String str = "";
                for (int i=0;i<n;i++) {
   
                    if (i==idx) str += 'Q';
                    else str += '.';
                }
                strlst.add(str);
            }
            res.add(strlst);
        }
        return res;
    }
}

Leetcode 题解 - 搜索

BFS

1. 计算在网格中从原点到特定点的最短路径长度

Leetcode-1091. 二进制矩阵中的最短路径

解法：

2. 组成整数的最小平方数数量

Leetcode-279. 完全平方数

解法：

3. 最短单词路径

Leetcode-127. 单词接龙

解法：

DFS

1. 查找最大的连通面积

Leetcode-695. 岛屿的最大面积

解法：

2. 矩阵中的连通分量数目

Leetcode-200. 岛屿数量

解法：

3. 好友关系的连通分量数目

547. 朋友圈

解法：

4. 填充封闭区域

Leetcode-130. 被围绕的区域

解法：

5. 能到达的太平洋和大西洋的区域

Leetcode-417. 太平洋大西洋水流问题

解法：

Backtracking

1. 数字键盘组合

Leetcode-17. 电话号码的字母组合

解法：

2. IP 地址划分

Leetcode-93. 复原IP地址

解法：

3. 在矩阵中寻找字符串

Leetcode-79. 单词搜索

解法：

4. 输出二叉树中所有从根到叶子的路径

Leetcode-257. 二叉树的所有路径

解法：

5. 排列

Leetcode-46. 全排列

解法：

6. 含有相同元素求排列

Leetcode-47. 全排列 II

解法：

7. 组合

Leetcode-77. 组合

解法：

8. 组合求和

Leetcode-39. 组合总和

解法：

9. 含有相同元素的组合求和

Leetcode-40. 组合总和 II

解法：

10. 1-9 数字的组合求和

Leetcode-216. 组合总和 III

解法：

11. 子集

Leetcode-78. 子集

解法：

12. 含有相同元素求子集

Leetcode-90. 子集 II

解法：

13. 分割字符串使得每个部分都是回文数

Leetcode-131. 分割回文串

解法：

14. 数独

Leetcode-37. 解数独

解法：

15. N 皇后

Leetcode-51. N皇后

解法：