🦋 回溯算法详解：从入门到精通
✨ 一文掌握回溯算法精髓：系统性搜索 + 智能剪枝 = 高效解题
🎯 核心思想：试错法 + 系统性搜索 + 剪枝优化
📚 适用场景：组合、排列、子集、棋盘、字符串匹配等问题
📖 目录
🎯 什么是回溯算法
回溯算法（Backtracking）是一种系统地搜索问题解的算法。它通过尝试所有可能的候选解来找出所有解，当发现当前候选解不可能是正确的解时，就放弃该候选解并回溯到上一步，尝试其他可能性。
核心思想
- 试错：尝试一种选择，如果不行就回退
- 系统性：按照某种顺序系统地搜索所有可能解
- 剪枝：提前排除不可能的分支，减少搜索空间
适用场景
- 组合问题：从N个数中找出满足条件的组合
- 排列问题：N个数按一定规则全排列
- 子集问题：N个数的满足条件的子集
- 棋盘问题：N皇后、数独等
- 字符串匹配：通配符匹配、正则表达式
🚀 快速入门指南
🎯 什么是回溯算法？
回溯算法 = 深度优先搜索(DFS) + 状态撤销
想象你在走迷宫：
- 🚶♂️ 向前走：选择一个方向继续前进
- 🚫 遇到死胡同：回退到上一个路口
- 🔄 尝试其他方向：选择另一个未尝试的方向
- ✅ 找到出口：记录成功路径
💡 核心三要素
| 要素 |
说明 |
示例 |
| 路径 |
已经做出的选择 |
path = [1, 3, 5] |
| 选择列表 |
当前可以做的选择 |
candidates = [2, 4, 6, 8] |
| 结束条件 |
何时停止搜索 |
sum >= target |
🔑 万能模板（记住这个就够了！）
1
2
3
4
5
6
7
8
9
10
11
12
| void backtrack(路径, 选择列表) {
if (满足结束条件) {
结果.add(路径);
return;
}
for (选择 : 选择列表) {
做选择(选择);
backtrack(新路径, 新选择列表);
回溯，撤销选择(选择);
}
}
|
🎨 举个简单例子：子集问题
求集合 [1, 2, 3] 的所有子集：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
private void backtrack(int[] nums, int index, List<List<Integer>> result, List<Integer> path) {
result.add(new ArrayList<>(path));
for (int i = index; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, result, path);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
if (nums == null || nums.length == 0) {
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtrack(nums, 0, result, path);
return result;
}
|
⚡ 一分钟理解回溯
- 做选择：在当前路口选择一个方向 ➡️
- 探索到底：沿着这个方向一直走下去 🏃♂️
- 回退撤销：遇到死胡同时回退 🔄
- 尝试新方向：选择另一个未尝试的方向 🔄
关键：撤销选择让你能够系统地探索所有可能性！
🏗️ 回溯算法的基本框架
通用模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class BacktrackingTemplate {
public void backtrack(路径, 选择列表, 结果) {
if (满足结束条件) {
结果.add(路径);
return;
}
for (选择 : 选择列表) {
路径.add(选择);
backtrack(路径, 新的选择列表, 结果);
路径.remove(选择);
}
}
}
|
框架解析
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 终止条件：到达决策树底层，无法再做选择的条件
- 回溯：撤销当前选择，回到上一步状态
🎯 解题四步法：系统攻克回溯问题
📝 步骤1：问题分析
🔍 关键问题：
- ❓ 选择是什么？ 每个决策点有哪些选项？
- ❓ 约束条件？ 什么情况下不能继续？
- ❓ 目标状态？ 什么情况下找到解？
🎨 示例：组合总和问题
1
2
3
| 选择：从candidates中选一个数字
约束：sum <= target（剪枝），数字可重复使用
目标：sum == target
|
🛠️ 步骤2：设计回溯函数
🎯 函数签名：backtrack(路径, 选择列表, 其他参数)
🧩 核心结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| private void backtrack(路径, 选择列表, 约束参数) {
if (满足结束条件) {
记录结果();
return;
}
for (选择 : 选择列表) {
if (!isValid(选择)) continue;
路径.add(选择);
backtrack(新路径, 新选择列表, 新约束);
路径.remove(选择);
}
}
|
⚡ 步骤3：剪枝优化
🔪 剪枝策略：
- 约束剪枝：违反约束直接返回
- 目标剪枝：无法达到目标直接返回
- 重复剪枝：避免重复计算相同状态
💡 剪枝口诀：
1
2
3
| 🎯 能剪就剪，绝不手软
🔍 提前判断，避免深搜
⚡ 减少分支，提升效率
|
🧪 步骤4：测试验证
✅ 测试用例设计：
- 边界情况：空输入、单元素、最大值
- 特殊情况：重复元素、无法解、多解
- 性能测试：大数据量、时间复杂度
🎯 验证要点：
- 结果是否正确？
- 是否去重？
- 是否剪枝？
- 时间复杂度？
🧩 经典问题详解：从理论到实战
🎯 学习目标：通过4个经典问题，掌握回溯算法的核心技巧
📊 难度梯度：⭐☆☆☆ → ⭐⭐☆☆ → ⭐⭐⭐☆ → ⭐⭐⭐⭐
💡 核心技巧：剪枝优化 + 去重处理 + 约束条件
1. 组合总和问题 ⭐☆☆☆
🎯 LeetCode 39：给定一个无重复元素的整数数组和一个目标和，找出所有可以使数字和为目标的组合。
💡 核心思路：每个数字可以重复使用，通过剪枝避免无效搜索
🎨 可视化：
1
2
3
4
5
6
7
8
9
10
| candidates = [2, 3, 6, 7], target = 7
🔍 搜索过程：
2 → 2 → 2 → 2 (sum=8 > 7) ❌ 剪枝
2 → 2 → 3 (sum=7 == 7) ✅ 找到解
2 → 2 → 6 (sum=10 > 7) ❌ 剪枝
...
7 (sum=7 == 7) ✅ 找到解
✨ 结果：[[2, 2, 3], [7]]
|
原始实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| public class CombinationSum {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backtrack(candidates, target, 0, 0);
return result;
}
private void backtrack(int[] candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
if (sum > target) {
return;
}
for (int i = startIndex; i < candidates.length; i++) {
path.add(candidates[i]);
sum += candidates[i];
backtrack(candidates, target, sum, i);
path.remove(path.size() - 1);
sum -= candidates[i];
}
}
}
|
优化实现：剪枝优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class CombinationSumOptimized {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backtrack(candidates, target, 0, 0);
return result;
}
private void backtrack(int[] candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) {
break;
}
path.add(candidates[i]);
backtrack(candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1);
}
}
}
|
2. 子集问题 ⭐⭐☆☆
LeetCode 78：给定一组不含重复元素的整数数组，返回其所有可能的子集（幂集）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class Subsets {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0);
return result;
}
private void backtrack(int[] nums, int startIndex) {
result.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
|
算法解析：
- 选择：对于每个元素，都有两种选择：选或不选
- 约束：无特殊约束，所有组合都有效
- 目标：生成所有可能的子集
- 关键：在递归开始就记录当前路径，因为每个状态都是有效子集
示例：
输入：[1, 2, 3]
输出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
3. 全排列问题 ⭐⭐⭐☆
LeetCode 46：给定一个没有重复数字的序列，返回其所有可能的全排列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| public class Permutations {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private boolean[] used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
backtrack(nums);
return result;
}
private void backtrack(int[] nums) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
|
4. N皇后问题 ⭐⭐⭐⭐
LeetCode 51：经典的N皇后问题，在N×N棋盘上放置N个皇后，使其不能互相攻击。
方法一：基础回溯算法
算法思路
为了确保皇后之间互不冲突，我们需要满足三个约束条件：列、主对角线和次对角线约束。
约束条件处理
1. 列约束
- 使用长度为
n 的布尔数组 cols，其中 cols[col] 表示第 col 列是否已被占用
- 在放置皇后前检查
cols[col]，若为 false 则可放置，否则剪枝
- 回溯时动态更新
cols 的状态
2. 主对角线约束
- 主对角线（左上到右下）上的所有格子满足 行索引 - 列索引 = 常数
- 使用长度为
2n - 1 的数组 diags1，其中 diags1[row - col + n - 1] 标记该对角线是否被占用
- 映射逻辑：
row - col 的范围为 [-(n-1), n-1]，通过 + n - 1 将其转换为非负索引 [0, 2n-2]
3. 次对角线约束
- 次对角线（右上到左下）上的所有格子满足 行索引 + 列索引 = 常数
- 使用长度为
2n - 1 的数组 diags2，直接以 row + col 作为索引（范围为 [0, 2n-2]）
优化要点
| 优化维度 |
具体实现 |
复杂度 |
| 空间优化 |
仅需 3 个数组（cols、diags1、diags2）即可覆盖所有约束 |
O(n) |
| 剪枝效率 |
每次放置前检查三个数组 |
O(1) |
| 索引映射 |
主对角线的 row - col 可能为负，通过 + n - 1 偏移确保数组访问合法 |
- |
具体示例
n = 4 时：
diags1 和 diags2 的长度均为 7（2 * 4 - 1）- 格子
(1, 2) 的主对角线索引：1 - 2 + 3 = 2；次对角线索引：1 + 2 = 3
这种设计以最小开销实现了对棋盘约束的精确控制，是回溯算法剪枝的经典实践。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
boolean[] cols = new boolean[n];
boolean[] diags1 = new boolean[2 * n - 1];
boolean[] diags2 = new boolean[2 * n - 1];
backtrack(0, n, board, res, cols, diags1, diags2);
return res;
}
private void backtrack(int row, int n, char[][] board, List<List<String>> res,
boolean[] cols, boolean[] diags1, boolean[] diags2) {
if (row == n) {
List<String> solution = new ArrayList<>();
for (char[] r : board) {
solution.add(new String(r));
}
res.add(solution);
return;
}
for (int col = 0; col < n; col++) {
int diag1 = row - col + n - 1;
int diag2 = row + col;
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
board[row][col] = 'Q';
cols[col] = diags1[diag1] = diags2[diag2] = true;
backtrack(row + 1, n, board, res, cols, diags1, diags2);
board[row][col] = '.';
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
}
|
方法二：基础回溯算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| public class NQueens {
private List<List<String>> result = new ArrayList<>();
private char[][] board;
private int n;
public List<List<String>> solveNQueens(int n) {
this.n = n;
this.board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0);
return result;
}
private void backtrack(int row) {
if (row == n) {
result.add(boardToList());
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
}
}
}
private boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
private List<String> boardToList() {
List<String> list = new ArrayList<>();
for (char[] row : board) {
list.add(new String(row));
}
return list;
}
}
|
✂️ 剪枝优化技巧
1. 排序剪枝
通过排序可以提前终止不可能的分支：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
for (int i = startIndex; i < candidates.length; i++) {
path.add(candidates[i]);
if (sum + candidates[i] > target) {
path.remove(path.size() - 1);
continue;
}
}
Arrays.sort(candidates);
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) {
break;
}
path.add(candidates[i]);
}
|
2. 重复性剪枝
处理有重复元素的情况：
1
2
3
4
|
if (i > startIndex && candidates[i] == candidates[i-1]) {
continue;
}
|
3. 可行性剪枝
提前判断当前路径是否可能达到目标：
🎯 情况1：剩余元素和不足以达到目标
1
2
3
4
5
|
int remainingMinSum = calculateMinSum(candidates, i);
if (sum + remainingMinSum > target) {
break;
}
|
🎯 情况2：剩余元素数量不足以满足选择数量要求
1
2
3
4
5
6
7
8
9
10
11
12
|
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
backtrack(result, path, k, i + 1, sum + i);
path.remove(path.size() - 1);
}
|
🎯 情况3：剩余元素无法满足特定约束条件
1
2
3
4
5
6
7
8
9
10
|
if (candidates.length - i < k - path.size()) {
break;
}
int remainingMaxSum = calculateMaxSum(candidates, i);
if (sum + remainingMaxSum < target) {
break;
}
|
🏢 实际应用案例
案例1：任务调度问题
场景描述：有N个任务，每个任务有截止时间和完成所需时间，安排任务执行顺序，使得尽可能多的任务按时完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| public class TaskScheduling {
private static class Task {
int deadline;
int duration;
int id;
Task(int id, int deadline, int duration) {
this.id = id;
this.deadline = deadline;
this.duration = duration;
}
}
private List<Integer> bestSchedule;
private int maxTasks;
public List<Integer> scheduleTasks(List<Task> tasks) {
bestSchedule = new ArrayList<>();
maxTasks = 0;
tasks.sort((a, b) -> a.deadline - b.deadline);
backtrack(tasks, new ArrayList<>(), 0, 0);
return bestSchedule;
}
private void backtrack(List<Task> tasks, List<Integer> currentSchedule,
int currentTime, int taskIndex) {
if (currentSchedule.size() > maxTasks) {
maxTasks = currentSchedule.size();
bestSchedule = new ArrayList<>(currentSchedule);
}
if (currentSchedule.size() + (tasks.size() - taskIndex) <= maxTasks) {
return;
}
for (int i = taskIndex; i < tasks.size(); i++) {
Task task = tasks.get(i);
if (currentTime + task.duration <= task.deadline) {
currentSchedule.add(task.id);
backtrack(tasks, currentSchedule, currentTime + task.duration, i + 1);
currentSchedule.remove(currentSchedule.size() - 1);
}
}
}
}
|
案例2：资源分配优化
场景描述：将有限的资源分配给多个项目，每个项目有不同的收益和资源需求，找到收益最大的分配方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| public class ResourceAllocation {
private static class Project {
int resourceNeeded;
int profit;
int id;
Project(int id, int resourceNeeded, int profit) {
this.id = id;
this.resourceNeeded = resourceNeeded;
this.profit = profit;
}
}
private int maxProfit;
private List<Integer> bestAllocation;
public List<Integer> allocateResources(List<Project> projects, int totalResource) {
maxProfit = 0;
bestAllocation = new ArrayList<>();
projects.sort((a, b) -> (b.profit * a.resourceNeeded - a.profit * b.resourceNeeded));
backtrack(projects, totalResource, new ArrayList<>(), 0, 0);
return bestAllocation;
}
private void backtrack(List<Project> projects, int remainingResource,
List<Integer> currentAllocation, int currentProfit, int startIndex) {
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
bestAllocation = new ArrayList<>(currentAllocation);
}
int remainingMaxProfit = calculateMaxPossibleProfit(projects, startIndex, remainingResource);
if (currentProfit + remainingMaxProfit <= maxProfit) {
return;
}
for (int i = startIndex; i < projects.size(); i++) {
Project project = projects.get(i);
if (project.resourceNeeded <= remainingResource) {
currentAllocation.add(project.id);
backtrack(projects, remainingResource - project.resourceNeeded,
currentAllocation, currentProfit + project.profit, i + 1);
currentAllocation.remove(currentAllocation.size() - 1);
}
}
}
private int calculateMaxPossibleProfit(List<Project> projects, int startIndex, int remainingResource) {
int profit = 0;
int resource = remainingResource;
for (int i = startIndex; i < projects.size() && resource > 0; i++) {
Project project = projects.get(i);
if (project.resourceNeeded <= resource) {
profit += project.profit;
resource -= project.resourceNeeded;
} else {
profit += project.profit * resource / project.resourceNeeded;
break;
}
}
return profit;
}
}
|
⚡ 性能分析
时间复杂度
回溯算法的时间复杂度通常是指数级的：
| 问题类型 |
时间复杂度 |
说明 |
| 子集问题 |
O(2^n) |
每个元素都有选或不选两种选择 |
| 排列问题 |
O(n!) |
n个元素的全排列 |
| 组合问题 |
O(C(n,k)) |
从n个元素中选择k个 |
| N皇后 |
O(n!) |
每行放置一个皇后 |
空间复杂度
- 递归栈空间：O(n) 到 O(h)，h是递归深度
- 路径存储：O(n) 存储当前路径
- 结果存储：O(所有解的总大小)
优化效果
通过剪枝优化可以显著减少实际搜索空间：
- 排序剪枝：通常可以减少50%以上的搜索节点
- 可行性剪枝：根据问题特性，可能减少90%以上
- 重复性剪枝：完全避免重复解的生成
🏋️ 实战练习
练习题1：电话号码的字母组合 📞
LeetCode 17：给定一个仅包含数字2-9的字符串，返回所有可能的字母组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| public class LetterCombinations {
private static final String[] LETTERS = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
private List<String> result;
private StringBuilder path;
public List<String> letterCombinations(String digits) {
result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
path = new StringBuilder();
backtrack(digits, 0);
return result;
}
private void backtrack(String digits, int index) {
if (index == digits.length()) {
result.add(path.toString());
return;
}
int digit = digits.charAt(index) - '0';
String letters = LETTERS[digit];
for (char letter : letters.toCharArray()) {
path.append(letter);
backtrack(digits, index + 1);
path.deleteCharAt(path.length() - 1);
}
}
}
|
练习题2：括号生成 🎯
LeetCode 22：数字n代表生成括号的对数，设计一个函数生成所有可能的且有效的括号组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public class GenerateParentheses {
private List<String> result;
private StringBuilder path;
public List<String> generateParenthesis(int n) {
result = new ArrayList<>();
path = new StringBuilder();
backtrack(n, n);
return result;
}
private void backtrack(int leftRemaining, int rightRemaining) {
if (leftRemaining == 0 && rightRemaining == 0) {
result.add(path.toString());
return;
}
if (leftRemaining > 0) {
path.append('(');
backtrack(leftRemaining - 1, rightRemaining);
path.deleteCharAt(path.length() - 1);
}
if (rightRemaining > leftRemaining) {
path.append(')');
backtrack(leftRemaining, rightRemaining - 1);
path.deleteCharAt(path.length() - 1);
}
}
}
|
练习题3：单词搜索 🔍
LeetCode 79：给定一个二维网格和一个单词，找出该单词是否存在于网格中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| public class WordSearch {
private static final int[][] DIRECTIONS = {{-1,0}, {1,0}, {0,-1}, {0,1}};
private char[][] board;
private String word;
private boolean[][] visited;
private int rows, cols;
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || word == null || word.length() == 0) {
return false;
}
this.board = board;
this.word = word;
this.rows = board.length;
this.cols = board[0].length;
this.visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == word.charAt(0)) {
if (backtrack(i, j, 0)) {
return true;
}
}
}
}
return false;
}
private boolean backtrack(int row, int col, int index) {
if (index == word.length() - 1) {
return true;
}
visited[row][col] = true;
for (int[] dir : DIRECTIONS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (isValid(newRow, newCol) && !visited[newRow][newCol] &&
board[newRow][newCol] == word.charAt(index + 1)) {
if (backtrack(newRow, newCol, index + 1)) {
visited[row][col] = false;
return true;
}
}
}
visited[row][col] = false;
return false;
}
private boolean isValid(int row, int col) {
return row >= 0 && row < rows && col >= 0 && col < cols;
}
}
|
练习题4：分割回文串 ✨
LeetCode 131：给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| public class PalindromePartitioning {
private List<List<String>> result;
private List<String> path;
private String s;
public List<List<String>> partition(String s) {
result = new ArrayList<>();
path = new ArrayList<>();
this.s = s;
backtrack(0);
return result;
}
private void backtrack(int startIndex) {
if (startIndex == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int end = startIndex; end < s.length(); end++) {
if (isPalindrome(startIndex, end)) {
String substring = s.substring(startIndex, end + 1);
path.add(substring);
backtrack(end + 1);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
|
📚 相关LeetCode题目
基础题目
进阶题目
高难度题目
🎯 关键要点总结
核心原则
- 明确选择：清楚地定义每一步的选择是什么
- 路径记录：维护当前的选择路径
- 终止条件：确定何时停止搜索
- 回溯机制：能够撤销选择，回到之前的状态
常见陷阱
- 忘记回溯：选择后忘记撤销，导致状态错误
- 重复选择：没有正确处理已选择的元素
- 边界条件：数组越界、空指针等边界问题
- 性能问题：没有剪枝导致搜索空间过大
优化策略
- 排序剪枝：先排序，提前终止不可能的分支
- 重复性剪枝：跳过重复的选择，避免重复解
- 可行性剪枝：提前判断当前路径是否可能成功
- 最优性剪枝：在优化问题中，提前判断是否可能超越当前最优解
调试技巧
- 打印路径：在关键节点打印当前路径
- 限制搜索：先处理小规模问题，验证算法正确性
- 可视化：画出决策树，帮助理解搜索过程
- 逐步调试：使用IDE的调试功能，逐步跟踪回溯过程
🎯 回溯算法模板总结
模板1：组合/子集问题 🧩
适用场景：从一组元素中选择若干个，不考虑顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public class CombinationTemplate {
private List<List<Integer>> result;
private List<Integer> path;
public List<List<Integer>> combine(int[] nums) {
result = new ArrayList<>();
path = new ArrayList<>();
backtrack(nums, 0);
return result;
}
private void backtrack(int[] nums, int startIndex) {
result.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
|
关键特征：
- 使用
startIndex避免重复选择
- 每个元素都有"选"或"不选"两种选择
- 时间复杂度：O(2^n)
模板2：排列问题 🔄
适用场景：考虑元素顺序的所有可能排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| public class PermutationTemplate {
private List<List<Integer>> result;
private List<Integer> path;
private boolean[] used;
public List<List<Integer>> permute(int[] nums) {
result = new ArrayList<>();
path = new ArrayList<>();
used = new boolean[nums.length];
backtrack(nums);
return result;
}
private void backtrack(int[] nums) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
path.add(nums[i]);
used[i] = true;
backtrack(nums);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
|
关键特征：
- 使用
used[]数组标记已使用元素
- 每个位置可以选择任意未使用的元素
- 时间复杂度：O(n!)
模板3：N皇后/棋盘问题 ♛
适用场景：在二维空间中寻找满足约束条件的解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| public class NQueensTemplate {
private List<List<String>> result;
private char[][] board;
private int n;
public List<List<String>> solveNQueens(int n) {
result = new ArrayList<>();
this.n = n;
this.board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(0);
return result;
}
private void backtrack(int row) {
if (row == n) {
result.add(boardToList());
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
}
}
}
private boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
}
|
关键特征：
- 按行/列顺序处理，避免重复
- 需要复杂的约束检查
- 时间复杂度：O(n!)
🧠 记忆口诀
🎯 回溯算法三步法
- 做选择：在当前状态下选择一个选项
- 递归探索：基于当前选择继续探索
- 撤销选择：回到选择前的状态
🔍 剪枝优化口诀
- 排序剪枝：“先排序，早剪枝”
- 约束剪枝：“不满足，就跳过”
- 最优剪枝：“不可能，就放弃”
🎨 问题分类记忆
- 组合问题：“选不选，startIndex”
- 排列问题：“用没用，used数组”
- 棋盘问题：“行不行，约束检查”
📖 参考资料
🎓 学习总结：回溯算法知识图谱
🗺️ 知识架构图
1
2
3
4
5
6
7
8
| 回溯算法 🌳
├── 核心思想 (DFS + 状态撤销)
├── 万能模板 (路径 + 选择列表 + 结束条件)
├── 解题四步法 (分析 → 设计 → 剪枝 → 验证)
├── 三大模板 (组合/子集 + 排列 + N皇后)
├── 四大经典 (组合总和 + 全排列 + N皇后 + 实际应用)
├── 优化技巧 (剪枝 + 去重 + 约束)
└── 实战练习 (LeetCode 经典题目)
|
🎯 掌握程度自测
| 掌握程度 |
标准 |
检验方式 |
| 入门 ⭐ |
理解基本概念，能看懂代码 |
解释什么是回溯算法 |
| 熟练 ⭐⭐ |
能独立解决基础问题 |
手写组合总和问题 |
| 精通 ⭐⭐⭐ |
掌握优化技巧，能举一反三 |
解决N皇后 + 剪枝优化 |
| 专家 ⭐⭐⭐⭐ |
能设计复杂算法，融会贯通 |
解决实际业务问题 |
🚀 进阶学习路线
- 🎯 基础巩固：熟练掌握三大模板
- ⚡ 技巧提升：深入学习剪枝和去重策略
- 🏗️ 实战应用：解决实际业务问题
- 🔬 算法研究：探索更高效的优化算法
💡 学习建议
1
2
3
4
5
| 📝 建议1：从简单问题入手，循序渐进
📝 建议2：多画图辅助理解，可视化搜索过程
📝 建议3：重视剪枝优化，提升算法效率
📝 建议4：总结模板套路，形成解题直觉
📝 建议5：刷题 + 总结，理论结合实践
|
最后更新：2025-01-15
