0. 回溯模版

a.迷宫问题

在棋盘上可以从任意起点出发，期望到达指定目的地。规定移动方向，比如向上下左右每次移动一格，棋盘中会有障碍物等，问是否能到达目的地。

遇到访问过的格子返回false，是因为在迷宫问题中，这一步是障碍物走不通，在单词搜索中不能走入之前走过的格子。

public boolean dfs(int i, int j, int pathNum){
    // base case: 结束条件
    // 把越界和访问过这些条件放在最外面
    if (i<0 || i>=N || j<0 || j>=M  || visited[i][j]){
        return false;
    }
    // 判断最后一步是否满足要求
    if (pathNum == word.length()-1){
        // 走到最后一步是否和word一致
        return board[i][j]==word.charAt(pathNum);
    }
    // 最后的结果
    boolean res = false;
    // 标记当前访问节点为visited, 做出了选择
    if(board[i][j]==word.charAt(pathNum)){
        visited[i][j] = true;
        // 4个dfs, 就是回溯的可能选择
        res =  dfs(i+1, j, pathNum+1) || dfs(i-1, j, pathNum+1)
                || dfs(i, j+1, pathNum+1) || dfs(i, j-1, pathNum+1);

        // 撤销选择
        visited[i][j] = false;
    }
    return res;
}

public static boolean dfs(char[][] board, int x, int y){
    int rows = board.length;
    int cols = board[0].length;
    // base case:
    // 在越界 和 是访问过的(也可以是障碍物) 返回false
    if (x<0 || x>rows-1 || y<0 || y>cols-1 || board[x][y] == '#'){
        return false;
    }
    // 判断是否到达终点
    if (board[x][y] == 'E'){
        return true;
    }
    // 做出选择
    board[x][y] = '#';
    // dfs的选择
    boolean res = dfs(board, x+1, y) || dfs(board, x-1, y)
                  || dfs(board, x, y+1) || dfs(board, x, y-1);
    // 拆回选择
    board[x][y] = '.';
    return res;
}

b.排列组合数学基础

参考资料知乎小小神兽

如果要想在 n 个物品中，按顺序的选择 k 个物品，那么选择的方式总共有这么多种：

如果要想在 n 个物品中，选择 k 个物品出来，选择的顺序无所谓，那么选择的方式总共有这么多种：

举个例子，
8个运动员中，颁发金银铜奖牌给三人，问有多少种可能的颁发结果？答案：P(8,3)
8个运动员中，颁发一样的奖牌给三人，问有多少种可能的颁发结果？答案：C(8,3)

对于第一个问题，8个人任选3个人之后，还要给那3个人排序。对于后一个问题，8个人任选3个人就完事了。因为三个人领取的金银铜奖牌还有不同的组合，所以C(8,3)相对于P(8,3)少了一个3的阶乘，这个3的阶乘就是三个人如何分配金银铜奖牌的组合。

比如在唯一路径问题中，求从棋盘(m*n)左上角到右下角的方法数（每次只能向下或向右走）？
利用组合的知识知道，所有的方法都需要走m+n步，从中选取m步向右走，方法总数就是C(m+n, m)，选取的这m步之间没有任何先后区别或者等级高低，所以不是排列问题。

再比如，有道题目中，给出二叉树某一深度的所有节点数为n，下一层的节点数为m，求组成二叉树的可能数量？
这也是一个组合问题，这一层的节点为n，那么下一层最多有2n个节点，从这2n个位置中选取m个组成二叉树，组合数目就是C(2n,m)，选取m个节点没有任何先后区别，所以不是排列问题。

c.子集排列组合

子集

求取子集问题，不用加终止条件，因为子集就是要遍历整个一棵树，不需要任何剪枝。

public static void backTracking(int[] nums, int start, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> path){
    // 前序遍历，在递归前加入答案
    res.add(new ArrayList<Integer>(path));
    // 对于子集的回溯模版，终止条件是自然的，选择列表中没有可选的
    for (int i = start; i < nums.length; ++i){
        // 做出选择
        path.add(nums[i]);
        // 每次调用自己的时候，记着要从i+1 开始
        backTracking(nums, i+1, res, path);
        // 撤销选择
        path.remove(path.size()-1);
    }
}

d.是动态规划还是回溯

动态规划是基于重叠子问题和最优子结构，从暴力递归出发，用空间换时间而找到的一种优化方法。通常问题是求方法数(比如机器人走棋盘)和最优解(走棋盘的最少步数和最长升序子序列)，这时候是采用动态规划，从底向上的解决问题。

回溯算法解决的问题一般用dfs或bfs穷尽所有可能的尝试，比如迷宫问题中的是否能到达终点。

遇到不同的问题要仔细分析。

1. 棋盘迷宫

公主和王子

Nr. 某公司笔试

题目描述：
在一个n行m列的二维地图中，王子的位置为(x1,y1)，公主的位置为(x2,y2)。
请在这里输入引用内容
在地图中设有一些障碍物，王子只能朝上、下、左、右四个方向行走，且不允许走出地图也不允许穿越障碍物。
请在这里输入引用内容
请编写一个程序判断王子是否可以顺利走到公主所在的位置。
其中S表示王子的位置，E表示公主的位置，'.'表示可以通行，'#'表示障碍物（不能通行）。

解题思路:
用回溯的思想，通过深度优先搜索(dfs)，从棋盘的王子的位置出发试图找到公主，条件完成就是能搜索到棋盘上的"E"。

public static boolean isFoundPrince(char[][] board){

    if (board == null || board.length == 0 || board[0].length==0){
        return false;
    }

    boolean res = false;
    for (int i = 0; i < board.length; i++){
        for (int j = 0; j < board[0].length; j++){
            // 找到王子的位置，开始dfs
            if (board[i][j] == 'S'){
                if (dfs(board, i, j)){
                    res = true;
                }
            }
        }
    }
    return res;
}

public static boolean dfs(char[][] board, int x, int y){
    int rows = board.length;
    int cols = board[0].length;
    // 在越界 和 是访问过的(也可以是障碍物) 返回false
    if (x<0 || x>rows-1 || y<0 || y>cols-1 || board[x][y] == '#'){
        return false;
    }
    // base case:
    if (board[x][y] == 'E'){
        return true;
    }
    // 做出选择
    board[x][y] = '#';
    boolean res = dfs(board, x+1, y) || dfs(board, x-1, y)
                  || dfs(board, x, y+1) || dfs(board, x, y-1);
    // 拆回选择
    board[x][y] = '.';
    return res;
}

单词搜索

Nr. 剑指 Offer 12. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
请在这里输入引用内容
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
请在这里输入引用内容
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

解题思路：
利用回溯的方法，进行深度优先搜索。注意设置一个访问可达表，记录是否走过这一格子。相比迷宫问题，这个单词搜索要记录走过的路径步数以匹配单词

// 利用回溯算法框架解决这个问题
public boolean exist(char[][] board, String word) {
    // 根据题意判断边界情况
    if (word==null || word.equals("")){
        return false;
    }
    // 初始化
    N = board.length;
    M = board[0].length;
    this.word = word;
    this.board = board;
    visited = new boolean[N][M];
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            // 任意点开始，只要有一个就可以
            // 在(i,j)点执行回溯, 只要有一个能成功就返回true
            if (dfs(i, j, 0)){
                return true;
            }
        }
    }
    // 没有一个成功
    return false;
}


public boolean dfs(int i, int j, int pathNum){
    // base case: 结束条件
    // 把越界和访问过这些条件放在最外面
    if (i<0 || i>=N || j<0 || j>=M  || visited[i][j]){
        return false;
    }
    // 判断最后一步是否满足要求
    if (pathNum == word.length()-1){
        // 走到最后一步是否和word一致
        return board[i][j]==word.charAt(pathNum);
    }
    // 最后的结果
    boolean res = false;
    // 标记当前访问节点为visited, 做出了选择
    if(board[i][j]==word.charAt(pathNum)){
        visited[i][j] = true;
        // 4个dfs, 就是回溯的可能选择
        res =  dfs(i+1, j, pathNum+1) || dfs(i-1, j, pathNum+1)
                || dfs(i, j+1, pathNum+1) || dfs(i, j-1, pathNum+1);

        // 撤销选择
        visited[i][j] = false;
    }
    return res;
}

回溯(力扣)