回溯算法
回溯就是在一棵决策树上做 DFS，边走边试，发现不合法或不值得继续时立刻回头。
核心思路
做回溯题时，不要上来就想代码，先把三件事想清楚：
- 路径里现在装的是什么。
- 每一层有哪些选择。
- 什么情况下可以停。
所谓回溯，本质上就是这套固定动作：
- 做选择。
- 递归进入下一层。
- 撤销选择。
如果你能把这三步稳定写出来，剩下无非就是加 used、加 start、加剪枝。
回溯题的三种基本形态
排列
- 顺序重要。
- 通常使用
used[]防止一个元素重复使用。 - 代表题：全排列
组合 / 子集
棋盘 / 路径搜索
通用 Go 模板
func backtrack(nums []int) [][]int {
res := [][]int{}
path := []int{}
var dfs func(start int)
dfs = func(start int) {
// 这里根据题意决定何时收集答案
res = append(res, append([]int{}, path...))
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return res
}这个模板最适合子集 / 组合类问题。真正写题时，重点不是背模板，而是明确：
- 结果是在前序位置收集，还是叶子位置收集。
- 下一层是
i+1、i，还是从0重新开始。
两个高频变体
全排列
func permute(nums []int) [][]int {
res := [][]int{}
path := make([]int, 0, len(nums))
used := make([]bool, len(nums))
var dfs func()
dfs = func() {
if len(path) == len(nums) {
res = append(res, append([]int{}, path...))
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
used[i] = true
path = append(path, nums[i])
dfs()
path = path[:len(path)-1]
used[i] = false
}
}
dfs()
return res
}组合总和式剪枝
import "sort"
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
res := [][]int{}
path := []int{}
var dfs func(start, sum int)
dfs = func(start, sum int) {
if sum == target {
res = append(res, append([]int{}, path...))
return
}
for i := start; i < len(candidates); i++ {
next := sum + candidates[i]
if next > target {
break
}
path = append(path, candidates[i])
dfs(i, next)
path = path[:len(path)-1]
}
}
dfs(0, 0)
return res
}这里最关键的优化就是“先排序，再剪枝”，否则搜索树会大很多。
易错点
回溯题大多数 bug 都不是算法错了，而是状态没恢复干净。
path加了元素之后，递归回来一定要弹出。used[i] = true之后，回溯回来一定要复原。- 组合题和排列题不要混用
start与used。 - 去重题要分清“树枝去重”和“树层去重”。
- 收集答案时要拷贝当前路径，不能直接把
path引用塞进结果。
学习顺序
相关主题
返回：算法学习导航