回溯
2025年5月22日大约 10 分钟
回溯
回溯算法是一种通过构建决策树来解决问题的算法。它通过逐步构建决策树，并在每个节点进行选择，然后递归地解决子问题，最后回溯到根节点，得到最终的解。
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}电话号码的字母组合 - LeetCode 17
class Solution {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits.length() == 0) {
return combinations;
}
Map<Character, String> phoneMap = new HashMap<>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
return combinations;
}
public void backtrack(List<String> combinations, Map<Character, String> phoneMap,
String digits, int index, StringBuffer combination) { // 五个参数：
// 1. 结果集 combinations
// 2. 电话号码对应的字母表 phoneMap
// 3. 当前遍历到的数字 digits
// 4. 当前遍历到的数字的索引 index
// 5. 当前遍历到的字母组合 combination
if (index == digits.length()) { // 终止条件：遍历完所有数字
combinations.add(combination.toString()); // 将当前字母组合添加到结果集
return;
}
char digit = digits.charAt(index); // 当前遍历到的数字
String letters = phoneMap.get(digit); // 当前遍历到的数字对应的字母
for (int i = 0; i < letters.length(); i++) { // 遍历当前数字对应的每个字母
combination.append(letters.charAt(i)); // 处理节点
backtrack(combinations, phoneMap, digits, index + 1, combination); // 递归
combination.deleteCharAt(index); // 回溯
}
}
}组合 - LeetCode 77
- removeLast() 是 LinkedList 的特有方法，ArrayList 没有。
- 也可以用 path.remove(path.size() - 1); 来代替 path.removeLast();
class Solution {
List<List<Integer>> result= new ArrayList<>(); // 结果集
LinkedList<Integer> path = new LinkedList<>(); // 当前组合
public List<List<Integer>> combine(int n, int k) { // n是范围[1,n]，k是个数的组合有几个
backtracking(n,k,1);
return result;
}
public void backtracking(int n,int k,int startIndex){
if (path.size() == k){ // 当前这条路径已经构成了一个合法的组合（满足题意），可以结束递归、保存结果了。
result.add(new ArrayList<>(path));
return;
}
for (int i =startIndex;i<=n;i++){ // 遍历当前组合的每个元素，i = startIndex 是为了避免重复选数，保证组合里是升序、不重复的。要从 1 到 n 里选数，包含 n 本身。
path.add(i); // 处理节点
backtracking(n,k,i+1); // 递归
path.removeLast(); // 回溯
}
}
}- 剪枝优化：
- 你在构造组合 [1, 2, ..., n] 中选 k 个数，当你已经选了一些数（path.size()），剩下还需要 k - path.size() 个。那就需要保证：从当前位置 i 开始，后面至少还剩 k - path.size() 个数可选，否则就不用继续循环了。
- i <= n - (k - path.size()) + 1;
组合总和 - LeetCode 39
// 剪枝优化
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 先进行排序，因为如果数组是升序的，那么如果当前的 sum + candidates[i] > target，那么后面的数也一定 > target，所以可以提前终止循环。
backtracking(res, new ArrayList<>(), candidates, target, 0, 0); // 参数：
// 1. 结果集 res
// 2. 当前组合 path
// 3. 候选数组 candidates
// 4. 目标值 target
// 5. 当前组合的和 sum
// 6. 当前遍历到的索引 idx
return res;
}
public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
// 如果 sum + candidates[i] > target 就终止遍历
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(res, path, candidates, target, sum + candidates[i], i);
path.removeLast(); // 回溯，移除路径 path 最后一个元素
}
}
}全排列 - LeetCode 46
- 组合问题不像排列问题，不强调顺序，比如
[1,2]和[2,1]是同一个组合，但[1,2]和[2,1]是两个不同的排列。 - 用一个路径 path 记录当前构造中的排列
- 每次尝试将 nums[i] 放入 path 中，继续往下递归
- 一旦构造完成一个合法长度的排列，就加入结果集
class Solution {
List<List<Integer>> result = new ArrayList<>(); // 结果集
LinkedList<Integer> path = new LinkedList<>(); // 当前排列
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) return result; // 如果数组为空，直接返回结果集
backtrack(nums, path); // 参数：
// 1. 候选数组 nums
// 2. 当前排列 path
return result;
}
public void backtrack(int[] nums, LinkedList<Integer> path) {
if (path.size() == nums.length) { // 终止条件：当前排列长度等于 nums 长度，说明已经构造完成一个合法长度的排列，可以加入结果集了。
result.add(new ArrayList<>(path)); // 要拷贝一份 因为path是引用，如果直接add(path)，那么result中的path会跟着path变化
return;
}
for (int i =0; i < nums.length; i++) { // 遍历候选数组 nums 中的每个元素
// 如果path中已有，则跳过
if (path.contains(nums[i])) continue; // 如果当前元素已经在 path 中，则跳过
path.add(nums[i]); // 处理节点
backtrack(nums, path); // 递归
path.removeLast(); // 回溯
}
}
}子集 - LeetCode 78
class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
List<Integer> path = new ArrayList<>(); // 当前子集路径
dfs(nums, 0, path);
return ans;
}
private void dfs(int[] nums, int index, List<Integer> path) {
ans.add(new ArrayList<>(path)); // 每到一个节点，都加入当前路径作为一个子集
for (int i = index; i < nums.length; i++) {
path.add(nums[i]); // 选择nums[i]
dfs(nums, i + 1, path); // 递归
path.remove(path.size() - 1); // 回溯，撤销选择
}
}
}N皇后 - LeetCode 51
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), n, 0, new HashSet<>(), new HashSet<>(), new HashSet<>()); // 参数：
// 1. 结果集 res
// 2. 当前路径 path
// 3. 棋盘大小 n
// 4. 当前行 row
// 5. 已放置皇后的列 cols
// 6. 主对角线 diag1
return res;
}
public void backtrack(List<List<String>> res, List<Integer> path, int n, int row,
Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
if (row == n) { // 终止条件：当前行 row 等于 n，说明已经放置了 n 个皇后，可以返回结果了。
res.add(buildBoard(path, n));
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue; // 如果当前列、主对角线、副对角线已被占用，则跳过
path.add(col); // 处理节点
cols.add(col); // 处理节点
diag1.add(row - col); // 处理节点
diag2.add(row + col); // 处理节点
backtrack(res, path, n, row + 1, cols, diag1, diag2); // 递归
path.remove(path.size() - 1); // 回溯
cols.remove(col); // 回溯
diag1.remove(row - col); // 回溯
diag2.remove(row + col); // 回溯
}
}
private List<String> buildBoard(List<Integer> path, int n) {
List<String> board = new ArrayList<>();
for (int col : path) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[col] = 'Q';
board.add(new String(row));
}
return board;
}
}N皇后II - LeetCode 52
- HashSet.contains(...) 是 O(1) 的，效率高很多 不用像list每次都遍历
class Solution {
public int totalNQueens(int n) {
Set<Integer> columns = new HashSet<>(); // 记录已放置皇后的列
Set<Integer> diagonals1 = new HashSet<>(); // 主对角线（左上 - 右下）: row - col
Set<Integer> diagonals2 = new HashSet<>(); // 副对角线（右上 - 左下）: row + col
return backtrack(n, 0, columns, diagonals1, diagonals2); // 参数：
// 1. 棋盘大小 n
// 2. 当前行 row
// 3. 已放置皇后的列 columns
// 4. 主对角线 diagonals1
// 5. 副对角线 diagonals2
}
public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
if (row == n) { // 终止条件：当前行 row 等于 n，说明已经放置了 n 个皇后，可以返回结果了。
return 1; // 把1返回给上一层，因为上一层是 count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
} else {
int count = 0;
for (int i = 0; i < n; i++) { // 遍历当前行的每个列
if (columns.contains(i)) continue; // 如果当前列 i 已被占用，则跳过
int diagonal1 = row - i; // 计算主对角线 左上 - 右下
if (diagonals1.contains(diagonal1)) continue; // 如果当前主对角线已被占用，则跳过
int diagonal2 = row + i; // 计算副对角线 右上 - 左下
if (diagonals2.contains(diagonal2)) continue; // 如果当前副对角线已被占用，则跳过
columns.add(i); // 处理节点
diagonals1.add(diagonal1); // 处理节点
diagonals2.add(diagonal2); // 处理节点
count += backtrack(n, row + 1, columns, diagonals1, diagonals2); // 递归
columns.remove(i); // 回溯
diagonals1.remove(diagonal1); // 回溯
diagonals2.remove(diagonal2); // 回溯
}
return count;
}
}
}括号生成 - LeetCode 22
- 没有for循环，因为括号生成是二叉树，每个节点有两种选择：添加左括号或添加右括号。
- 左括号数量小于 max，则可以添加左括号
- 右括号数量小于左括号数量，则可以添加右括号
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
backtrack(ans, new StringBuilder(), 0, 0, n); // 参数：
// 1. 结果集 ans
// 2. 当前括号 cur
// 3. 左括号数量 open
// 4. 右括号数量 close
// 5. 括号数量 max 记住'('和')'加起来算一个括号
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
if (cur.length() == max * 2) { // 终止条件：当前括号长度等于 max * 2，说明已经构造完成一个合法长度的括号，可以加入结果集了。
ans.add(cur.toString());
return;
}
if (open < max) { // 如果左括号数量小于 max，则可以添加左括号
cur.append('(');
backtrack(ans, cur, open + 1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) { // 如果右括号数量小于左括号数量，则可以添加右括号 因为，任何位置上，右括号数量不能多于左括号数量，否则就出现了 ")(" 这种错误顺序，括号不匹配。
cur.append(')');
backtrack(ans, cur, open, close + 1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
}单词搜索 - LeetCode 79
class Solution {
int rows, cols; // 棋盘的行数和列数
char[][] board; // 棋盘
String word; // 要匹配的单词
public boolean exist(char[][] board, String word) {
this.board = board;
this.word = word;
rows = board.length;
cols = board[0].length;
for (int i = 0; i < rows; i++) { // 遍历棋盘的每行
for (int j = 0; j < cols; j++) { // 遍历棋盘的每列
if (dfs(i, j, 0)) { // 从board[i][j]开始，匹配word的第0个字符
return true;
}
}
}
return false;
}
// 从board[i][j]开始，匹配word的第index个字符
private boolean dfs(int i, int j, int index) { //index表示当前匹配到word的第几个字符
// 如果所有字符都匹配成功，返回true
if (index == word.length()) return true;
// 边界条件和字符匹配检查
if (i < 0 || i >= rows || j < 0 || j >= cols
|| board[i][j] != word.charAt(index)) return false;
// 标记当前格子为访问过（临时修改字符）
char temp = board[i][j];
board[i][j] = '#';
// 四个方向探索 index+1 表示匹配下一个字符
boolean found = dfs(i+1, j, index+1)
|| dfs(i-1, j, index+1)
|| dfs(i, j+1, index+1)
|| dfs(i, j-1, index+1);
// 回溯，恢复字符
board[i][j] = temp;
return found;
}
}复原IP地址 - LeetCode 93
class Solution {
String[] temp = new String[4]; // 存储IP地址的四个部分
List<String> ans = new ArrayList<>(); // 存储结果
public List<String> restoreIpAddresses(String s) {
if (s.length() < 4 || s.length() > 12) { // 如果长度小于4或者大于12，则返回空列表
return ans;
}
dfs(0, s, 4); // 从第0个字符开始，深度为4（表示还要填4个部分）
return ans;
}
public void dfs(int index, String s, int deep) {
if (deep == 0) { // 如果深度为0，则说明已经找到了四个部分
if (index == s.length()) { // 如果已经遍历完了字符串，则将结果添加到列表中
ans.add(String.join(".", temp)); // 将四个部分用"."连接起来 比如"1.2.3.4"
}
return;
}
for (int i = index; i <= s.length() - deep; i++) { // 从index开始，深度为deep
String sub = s.substring(index, i + 1); // 截取字符串
if ((sub.length() > 1 && sub.charAt(0) == '0') || Integer.parseInt(sub) > 255) { // 如果长度大于1且第一个字符为0，或者整数大于255，则跳过，因为之后更长的数字也一定非法
break;
}
temp[4 - deep] = sub; // 将截取的字符串添加到temp中
dfs(i + 1, s, deep - 1); // 递归调用，深度减1
}
}
}