回溯(力扣)
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;
} 
国家电网工作强度 101人发布