回溯算法本质上是一种深度优先搜索（DFS），通过递归来模拟“探索所有可能性”的过程。它的核心思想可以总结为三个步骤：
- 选择 (Choose): 在当前状态下，从所有可能的选择中，选择一个。
- 探索 (Explore): 基于这个选择，进入下一层决策，即调用递归函数。
- 撤销选择 (Unchoose): 当下一层的探索全部结束后（无论是找到了解还是走到了死路），退回到当前状态，撤销刚才的选择，然后尝试下一个可用的选择。
几乎所有的回溯问题，都可以用下面这个伪代码模板来解决：
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
| result = [] // 存放最终结果
path = [] // 存放当前路径
func backtrack(参数列表) {
// 1. 终止条件：判断是否找到了一个可行的解
if (满足结束条件) {
// 将当前路径的一个副本加入结果集
result.add(path.clone())
return
}
// 2. 遍历所有可能的选择
for choice in (当前状态下的所有选择) {
// 剪枝：如果这个选择不合法，则跳过
if (isPruned(choice)) {
continue
}
// 3. 做出选择
path.add(choice)
// 4. 进入下一层决策
backtrack(更新后的参数列表)
// 5. 撤销选择
path.removeLast()
}
}
|
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
| func permute(nums []int) [][]int {
ans := make([][]int, 0)
n := len(nums)
path := make([]int, n)
visited := make([]bool, n) // 回溯窗口
var dfs func(int)
dfs = func(idx int) {
if idx == n {
ans = append(ans, slices.Clone(path))
return
}
for i, visit := range visited {
if !visit {
visited[i] = true
path[idx] = nums[i] // 因为要得到全排列，所以不能从 path 中删除元素
dfs(idx + 1)
visited[i] = false
}
}
}
dfs(0)
return ans
}
|
该题是非常标准的回溯题，只在套路代码上加了一个 visited 数组用来记录选择结果。
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
| func combinationSum(candidates []int, target int) [][]int {
n := len(candidates)
ans := make([][]int, 0)
path := make([]int, 0)
var dfs func(idx, leftSum int)
dfs = func(idx, leftSum int) {
if leftSum == 0 {
ans = append(ans, slices.Clone(path))
}
if leftSum < 0 || idx >= n {
return
}
for i := idx; i < n; i++ {
path = append(path, candidates[i])
dfs(i, leftSum-candidates[i])
path = path[:len(path)-1]
}
}
dfs(0, target)
return ans
}
|
为了避免产生重复的组合需要在递归时传入一个起始索引，规定下一次搜索只能从这个索引及之后的元素中选择。该题在 dfs 函数中额外加上一个入参 leftSum 表示剩余和，代表选择的结果。
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
| func generateParenthesis(n int) []string {
path := make([]byte, 2*n)
ans := make([]string, 0)
var dfs func(int, int)
dfs = func(position, left int) {
if position == n*2 {
ans = append(ans, string(path))
return
}
// 只填左括号，不填右括号
if left < n {
path[position] = '('
dfs(position+1, left+1)
}
// 只填右括号，不填左括号
if position-left < left {
// 覆盖之前的选择，相当于回溯
path[position] = ')'
dfs(position+1, left)
}
}
dfs(0, 0)
return ans
}
|
该题就是回溯套路的变种，因为此类题的选择面临两个，之前的两道题都是单一的选择某个数然后放进 path ，但是此题不一样，必须对每一个选择进行一次选择-dfs-回溯流程。
先是选择左括号，然后 dfs，最后进行了隐式回溯（在后面第二次选择中前前次选择的结果进行了覆盖）。当左括号数量达到预定数量后，开始选择右括号，执行选择-dfs-回溯流程。
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
| func exist(board [][]byte, word string) bool {
directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
m, n := len(board), len(board[0])
var dfs func(i, j, idx int) bool
dfs = func(i, j, idx int) bool {
if idx == len(word) {
return true
}
if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[idx] {
return false
}
tmp := board[i][j]
board[i][j] = 0
for _, direction := range directions {
ni, nj := i+direction[0], j+direction[1]
if dfs(ni, nj, idx+1) {
return true
}
}
board[i][j] = tmp
return false
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if board[i][j] == word[0] {
if dfs(i, j, 0) {
return true
}
}
}
}
return false
}
|
与排列问题类似，需要标记访问过的节点以防走回头路。别忘记将原地修改的 board[i][j] 恢复成原来的字符 tmp。
当遇到一个新问题，感觉可能要用回溯时，按以下步骤思考：
- 明确
path 和 result：path 是什么（你正在构建的单个解）？result 是什么（最终要返回的所有解的集合）？ - 定义递归函数签名：思考
dfs 函数需要哪些参数来描述当前的状态？- 对于组合/排列问题，通常需要
startIndex 或 visited 数组。 - 对于构造问题，需要记录构造状态的参数（如 LC22 中的
left 括号数）。 - 对于网格问题，需要当前坐标
(i, j) 和匹配进度 idx。
- 确定终止条件：递归什么时候结束？
- 是找到了一个完整的解？（例如
path 长度足够，target 减为 0） - 还是走到了非法的状态，需要提前返回？（例如越界，数字和为负）
- 确定选择列表和剪枝逻辑：在当前状态下，你有哪些选择？这些选择中，有没有哪些可以提前判断为无效而直接跳过（剪枝）？
- 完成三部曲：在循环/选择分支中，清晰地写出“做出选择 -> 递归 -> 撤销选择”这三步。