回溯算法
本文详细解析了回溯算法的核心思想与适用场景:它本质上是带有状态重置的深度优先搜索,
简介
回溯算法是对树形或者图形结构执行一次深度优先遍历,实际上类似枚举的搜索尝试过程,在遍历的过程中寻找问题的解。
深度优先遍历有个特点:当发现已不满足求解条件时,就返回,尝试别的路径。此时对象类型变量就需要重置成为和之前一样,称为「状态重置」。
许多复杂的,规模较大的问题都可以使用回溯法,有「通用解题方法」的美称。实际上,回溯算法就是暴力搜索算法,它是早期的人工智能里使用的算法,借助计算机强大的计算能力帮助我们找到问题的解。
力扣相关算法题:https://leetcode.cn/tag/backtracking/problemset/
例题
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:
输入: digits = "23"
输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入: digits = ""
输出: []
示例 3:
输入: digits = "2"
输出: ["a","b","c"]
提示:
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解法:回溯算法用于寻找所有的可行解,如果发现一个解不可行,则会舍弃不可行的解。在这道题中,由于每个数字对应的每个字母都可能进入字母组合,因此不存在不可行的解,直接穷举所有的解即可。
该字符串初始为空。每次取电话号码的一位数字,从哈希表中获得该数字对应的所有可能的字母,并将其中的一个字母插入到已有的字母排列后面,然后继续处理电话号码的后一位数字,直到处理完电话号码中的所有数字,即得到一个完整的字母排列。然后进行回退操作,遍历其余的字母排列。
java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 17. 电话号码的字母组合
* https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
*
* @author Salmon
* @since 2023-12-10
*/
public class M_17 {
public static void main(String[] args) {
List<String> strings = letterCombinations("23");
for (String string : strings) {
System.out.printf("%s ", string);
}
}
static Map<Character, String> keyMap = new HashMap<Character, String>() {{
put('1', " ");
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
public static List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits.length() == 0) {
return res;
}
backtrack(res, digits, 0, new StringBuffer());
return res;
}
/**
* 回溯法
*
* @param res 结果集
* @param digits 待处理字符串
* @param index 当前下标
* @param sb 用户缓存当前已经匹配组合的字符串
*/
private static void backtrack(List<String> res, String digits, int index, StringBuffer sb) {
if (index == digits.length()) {
res.add(sb.toString());
return;
}
// 当前号码
char digit = digits.charAt(index);
// 获取当前号码对应的字母
String letters = keyMap.get(digit);
int lettersCount = letters.length();
// 遍历当前每个字母
for (int i = 0; i < lettersCount; i++) {
// 先将当前字母拼接上去,然后使用回溯法进行匹配,直到 index 到 输入的最后一个数字的下标位置
sb.append(letters.charAt(i));
backtrack(res, digits, index + 1, sb);
// 匹配完成后,则把 sb 缓存清空,接着匹配下一个字母开头的字符串
sb.deleteCharAt(index);
}
}
}

括号生成
题目:22. 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入: n = 1
输出: ["()"]
提示:
1 <= n <= 8
解法
java
import java.util.ArrayList;
import java.util.List;
/**
* 22. 括号生成
* https://leetcode.cn/problems/generate-parentheses/
*
* @author Salmon
* @since 2023-12-10
*/
public class M_22 {
public static void main(String[] args) {
List<String> strings = generateParenthesis(3);
for (String string : strings) {
System.out.println(string);
}
}
public static List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if (n == 0) {
return res;
}
dfs(new StringBuffer(), n, n, res);
return res;
}
/**
* 深度优先遍历
*
* @param curStr 当前递归得到的结果
* @param left 左括号还有几个可以使用
* @param right 右括号还有几个可以使用
* @param res 结果集
*/
private static void dfs(StringBuffer curStr, int left, int right, List<String> res) {
if (left == 0 && right == 0) {
res.add(curStr.toString());
return;
}
// 如果左右可使用的括号数量不匹配,剪枝(左括号可以使用的个数严格大于右括号可以使用的个数,才剪枝,注意这个细节)
if (left > right) {
return;
}
if (left > 0) {
curStr.append("(");
int length = curStr.length();
dfs(curStr, left - 1, right, res);
// 回溯,回到还没 添加 ( 之前
curStr.setLength(length - 1);
}
if (right > 0) {
curStr.append(")");
int length = curStr.length();
dfs(curStr, left, right - 1, res);
// 回溯,回到还没 添加 ) 之前
curStr.setLength(length - 1);
}
}
}

单词搜索
题目:79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1:

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出: true
示例 2:

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出: true
示例 3:

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出: false
提示:
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
解法
java
/**
* 79. 单词搜索
* https://leetcode.cn/problems/word-search/
*
* @author Salmon
* @since 2023-12-10
*/
public class M_79 {
public static void main(String[] args) {
char[][] board = {new char[]{'A', 'B', 'C', 'E'}, new char[]{'S', 'F', 'C', 'S'}, new char[]{'A', 'D', 'E', 'E'}};
String word = "ABCCED";
System.out.println(exist(board, word));
}
public static boolean exist(char[][] board, String word) {
// 获取网格的宽高
int height = board.length, width = board[0].length;
// 标记每个格子是否访问过
boolean[][] visited = new boolean[height][width];
// 从第一个格子逐一判断是否能构成单词
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
boolean flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
/**
* 校验
*
* @param board 网格数组
* @param visited 已经拜访过的格子
* @param i 当前待校验的格子在哪一行
* @param j 当前待校验的格子在哪一列
* @param s 单词
* @param k 判断当前单词中的哪个字符
* @return 是否匹配
*/
private static boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
// 如果当前格子与当前待匹配的字符不匹配
if (board[i][j] != s.charAt(k)) {
return false;
}
// 如果当前匹配到最后一个串,说明匹配结束
if (k == s.length() - 1) {
return true;
}
// 标记该网格已经访问过,防止接下来递归重新访问该网格
visited[i][j] = true;
// 定义一个方向数组,让每个格子分别往上下左右走走
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean result = false;
for (int[] dir : directions) {
// 接下来要访问的格子
int ni = i + dir[0], nj = j + dir[1];
// 防止下标越界
if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
// 判断该格子是否被访问过
if (!visited[ni][nj]) {
boolean flag = check(board, visited, ni, nj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
// 回溯,重新标记网格未访问,让其它路经可进过
visited[i][j] = false;
return result;
}
}
N皇后
题目:51. N皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1:

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:[["Q"]]
提示:
1 <= n <= 9
解法
java
import java.util.*;
/**
* 51.N皇后
* https://leetcode.cn/problems/n-queens/description/
*
* @author Salmon
* @since 2024-02-26
*/
public class D_51 {
List<List<String>> res = new ArrayList<>();
int n;
boolean[][] board; // 棋盘(记录哪里放棋
HashSet<Integer> col, pie, na;
public static void main(String[] args) {
D_51 d51 = new D_51();
System.out.println(d51.solveNQueens(4));
}
public List<List<String>> solveNQueens(int n) {
this.n = n;
this.board = new boolean[n][n];
this.col = new HashSet<>();
this.pie = new HashSet<>();
this.na = new HashSet<>();
dfs(0);
return res;
}
// 深度访问,由于n皇后问题是每一行,每一列,同一斜线上,都不能有皇后,故每一行只能有一个皇后
// 而将皇后放在哪一列,与对是否在斜线的判断,则在每一层进入的时候进行判断
public void dfs(int i) { // level 层,行
if (i == n) {
// 到最后一行,生成结果
generate_result();
return;
}
for (int j = 0; j < n; j++) {
if (col.contains(j) || pie.contains(i + j) || na.contains(i - j)) {
continue;
}
board[i][j] = true; // 标记当前访问过,当前位置放皇后
col.add(j); // 当前列访问了,则下一次就不能再访问了
pie.add(i + j); // 下一个是i+1,j+1,两者相加的值是个常量,而这条斜线上点的横纵坐标和都等于该值
na.add(i - j);// 下一个是 i-1,j-1 两者的和或差也可以代表某个点是否在这条斜线上,由于上边取的和,这里就取差
dfs(i + 1); // 进入下一层
col.remove(j);
pie.remove(i + j);
na.remove(i - j);
board[i][j] = false; // 走完了,重新标记未访问过
}
}
/**
* 生成结果
*/
private void generate_result() {
List<String> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
if (board[i][j]) {
sb.append("Q");
} else {
sb.append(".");
}
}
list.add(sb.toString());
}
res.add(list);
}
}
