回溯法 采用试错的思想，它尝试分步的去解决一个问题。
在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。
回溯法通常在解空间树上进行搜索，一般依赖的两种数据结构：子集树和排列树
子集树问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树,遍历子集树需O(2^n)计算时间
排列树问题是确定n个元素满足某种性质的排列时，相应的解空间树,遍历排列树需要O(n!)计算时间
设计思路
1.做题的时候，建议先画树形图，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。
在画图的过程中思考清楚：
- 分支如何产生；
- 题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
- 哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
【应用】[中等]单词搜索
题目描述：
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
// 回溯,时间复杂度O(MN*3的L次方),空间复杂度O(MN),M、N分别是board的行数、列数；L是word的长度
public boolean exist(char[][] board, String word) {
int h = board.length, w = board[0].length;
// 创建一个二维布尔数组用于记录当前位置是否被访问过
boolean[][] visited = new boolean[h][w];
// 遍历二维数组
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
// 调用check方法检查当前位置是否可以匹配word字符串的第一个字符，如果可以则继续
boolean flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
// 如果没有匹配成功，返回false
return false;
}
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
// 如果当前字符不等于字符串s的第k个字符，返回false
if (board[i][j] != s.charAt(k)) {
return false;
} else if (k == s.length() - 1) {
// 如果字符串s的所有字符都匹配，返回true
return true;
}
// 标记当前位置被访问
visited[i][j] = true;
// 定义4个方向
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean result = false;
// 遍历4个方向
for (int[] dir : directions) {
int newi = i + dir[0], newj = j + dir[1];
if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
// 新的位置没有被访问
if (!visited[newi][newj]) {
// 递归调用check函数
boolean flag = check(board, visited, newi, newj, s, k + 1);
// 如果匹配，返回true
if (flag) {
result = true;
break;
}
}
}
}
// 标记当前位置没有被访问
visited[i][j] = false;
return result;
}发布于 2024-03-22 13:00・IP 属地北京