【算法】回溯算法（二）：五个坑与一次验收——决策、切片与去重
【算法】回溯算法（二）：五个坑与一次验收——决策、切片与去重 摘要 回溯系列第二篇，翻车实录上半场。上一篇沉淀的模板十分钟就能背下来，但背下来和会用是两回事——本篇记录我在五道题上真实翻车的经历：决策粒度过粗（括号生成缺解）、Go 切片引用（全排列丢一半结果）、"要/不要"模型滥用（三道题同一个错）、同层去重（同一考点三次没接住，含 [1,2,2] 怎么生成的 8 条路径推演）、范式识别（该用 D
文章信息
- 原文链接：https://jiayq.blog.csdn.net/article/details/164337469
- 发布时间：2026-09-16 16:37:42
- 标签：#Golang, #算法, ##回溯决策
【算法】回溯算法（二）：五个坑与一次验收——决策、切片与去重
摘要
回溯系列第二篇，翻车实录上半场。上一篇沉淀的模板十分钟就能背下来，但背下来和会用是两回事——本篇记录我在五道题上真实翻车的经历：决策粒度过粗 （括号生成缺解）、Go 切片引用 （全排列丢一半结果）、“要/不要”模型滥用 （三道题同一个错）、同层去重 （同一考点三次没接住，含 [1,2,2] 怎么生成的 8 条路径推演）、范式识别 （该用 DP 的题硬上回溯）。每个坑都有错误代码、实测证据和修正方案，最后用 LC842 斐波那契拆分做一次毕业验收。坑虽多，主题只有两个：决策怎么设计、重复怎么消灭 。
说明，以下环境基于 go1.21+，题目均来自 LeetCode。前置阅读：回溯算法（一）：从一道 IP 题到万能模板。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode
系列篇目：
- 一、从一道 IP 题到万能模板
- 二、五个坑与一次验收——决策、切片与去重（本篇）
- 三、三记重锤与 N 皇后——记忆化、状态设计与三层漏斗
1. 翻车一：决策粒度（LC22 括号生成）
1.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
func generateParenthesis(n int) []string {
var gener func(s string)
res := make([]string, 0)
gener = func(s string) {
if len(s) == n*2 {
res = append(res, s)
return
}
for idx := len(s)/2; idx <= n; idx++ {
tmpS, right := "", ""
if len(s) >= 2*idx { // 这行是硬凑的，我自己都说不清为什么
continue
}
for i := 0; i < idx; i++ { // 一次造一整块 "(((...)))"
tmpS += "("
right += ")"
}
s += tmpS + right
gener(s)
s = s[:len(s)-idx*2]
}
}
gener("")
return res
}
跑出来：n=2 只输出 [(())]，缺 ()()；n=3 只输出 2 个，缺 3 个。
1.2 为什么缺解
这个模型每层塞进去的是一块已经配好对 的 ((()))，它只能生成”完整块的顺序拼接”。但合法括号串的本质结构是嵌套 ，看 (()())：
1
2
(()()) = "(" + "()" + ")" + "()"
它没法分解成若干个”各自配对完整的块”的拼接——在这个决策树里，它根本没有对应的路径 。所以缺解。
1.3 正确姿势：看着答案长出来
后来我学到一个方法：别盯着代码想决策，盯着一个最终答案，模拟它怎么一步步”长”出来——每长出一个原子单元，就是一层递归 。
(()()) 的长法：位置 0 放 ( → 位置 1 放 ( → 位置 2 放 ) → …… 每层放一个字符 。配上两个计数约束：
想放| 前提| 含义
—|—|—
(| open < n| 左括号没超预算
)| close < open| 任何前缀里右括号不能多于左括号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func generateParenthesis(n int) []string {
res := []string{}
var backtrack func(path []byte, open, close int)
backtrack = func(path []byte, open, close int) {
if len(path) == 2*n {
res = append(res, string(path)) // string() 转换本身就是拷贝
return
}
if open < n {
path = append(path, '(')
backtrack(path, open+1, close)
path = path[:len(path)-1]
}
if close < open {
path = append(path, ')')
backtrack(path, open, close+1)
path = path[:len(path)-1]
}
}
backtrack([]byte{}, 0, 0)
return res
}
close < open 这条约束保证了走到叶子的每条路径都合法——把合法性编码进选择条件，非法分支压根不进树。
记住这个直觉：决策里出现”循环构造一段东西”，几乎必然粒度过大 。这是血的教训。
2. 翻车二：Go 切片引用（LC46 全排列）
这个坑和算法无关，但 Go 玩回溯必踩。我写的全排列：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func permute(nums []int) [][]int {
res := make([][]int, 0)
var backtrack func(path []int)
backtrack = func(path []int) {
if len(path) == len(nums) {
res = append(res, path) // ← bug 在这一行
return
}
for _, v := range nums {
if isHave(path, v) {
continue
}
path = append(path, v)
backtrack(path)
path = path[:len(path)-1]
}
}
backtrack([]int{})
return res
}
逻辑全对，但 res = append(res, path) 存进结果的是切片头（指针+len+cap），不是数据快照 。回溯继续跑，path 的底层数组被原地覆盖写，之前收集的结果跟着一起变。
2.1 实测证据
加上指针追踪跑一遍，铁证如山：
1
2
3
4
5
6
7
8
9
10
11
收集时刻: [5 4 6 2] 底层数组=0x...180
收集时刻: [5 4 2 6] 底层数组=0x...180 ← 和上一个指向同一块内存！
收集时刻: [5 6 4 2] 底层数组=0x...1c0
收集时刻: [5 6 2 4] 底层数组=0x...1c0
...
=== permute 返回后，最终 res 内容 ===
res[0] = [5 4 2 6] ← 本应是 [5 4 6 2]，被覆盖了！
res[1] = [5 4 2 6]
res[2] = [5 6 2 4] ← 本应是 [5 6 4 2]，被覆盖了！
...
24 个结果两两重复，只剩 12 个不同值，一半的排列永久丢失 。
2.2 原因：append 的扩容轨迹
path 长度从 0 涨到 4，底层数组经历 cap 0 → 1 → 2 → 4 三次扩容。关键在第三次：进入第三层递归时扩容出的 cap=4 数组，被”前两段固定”的所有选择复用 ——第三段从 6 换成 2 时是原地覆盖写（cap 足够，不重新分配）。两次收集指向同一个数组，数组残留最后一次写入的值。
2.3 修复：一行
1
2
3
4
5
6
7
if len(path) == len(nums) {
tmp := make([]int, len(path))
copy(tmp, path) // 收集时拷贝快照，切断与回溯共享数组的联系
res = append(res, tmp)
return
}
go1.21+ 可以直接 res = append(res, slices.Clone(path))。
一个经验：string 收集不需要拷贝 （Go 的 string 不可变，append(res, s) 天然安全），必须拷贝的是可变类型 （slice / []byte）。所以回溯的 path 用 []byte，收集时 string(path) 一步到位——转换本身就是拷贝。这也解释了为什么括号生成那版没踩这个坑：string(path) 顺手把拷贝做了。
3. 翻车三：”要/不要”的滥用（LC47 / LC17）
我在子集、全排列 II、电话号码三道题上犯了同一个 错：把”要/不要”当万能模型。
3.1 全排列不是”要不要”
我给 LC47 设计的决策是”每个元素要不要进结果集”。但全排列要求所有元素都用上 ——终止条件是”所有元素都在临时结果集里”。那”不要”的分支走到最后怎么满足终止条件？自相矛盾了 。
排列的正确决策是每个位置选一个没用过的元素 （或者反过来，每个元素选一个位置）。
3.2 电话号码不是”要不要”
LC17 我设计成”每个字母取不取”，比如 ad = a 取、b 不取、c 不取、d 取、e 不取、f 不取。但既然”都不取”对每个字母都是合法决策，那 2 的 a/b/c 都不取 这条路径就存在——可输出里没有”只有 d”的答案。模型自己打自己。
事实是：每个数字必须恰好贡献一个字母 ，位置不能空着。决策是”选一个”：每层面对一个数字，从它对应的字母里必选其一。
3.3 病根
读题后先做一个 10 秒判断：“这个位置能空着吗？” 不能空（电话的数字必须贡献字母、排列的每个位置必须有数）→ 选一个；能空（子集里元素可以不进）→ 要/不要。一句话能避免三次翻车。
4. 翻车四：去重三连漏（LC47 → LC40 → LC90）
这是我最顽固的坑，同一考点三次没接住。
4.1 结果级去重为什么不行
LC47 时我的方案是”收集时查重，结果集里已存在就忽略”；LC90 时我又说”不排序，结果集去重，简单实现”。两个问题：
- 树照样全走 ，重复子树整棵白搜，指数级的路白跑
- 实现上恰恰更复杂 ：结果级去重要把每个子集序列化成 key 存哈希（排序拼字符串或数组做 map key），而树层去重只需要一行 if
4.2 同层去重：三题一表
三道题，同一个考点，三种载体：
| 题 | 模型 | 去重条件 | 前提 |
|---|---|---|---|
| 47 全排列 II | 选一个 + used | nums[i]==nums[i-1] && !used[i-1] → skip | 排序 |
| 40 组合总和 II | 选一个 + start | i > start && nums[i]==nums[i-1] → skip | 排序 |
| 90 子集 II | 要/不要 | i>0 && nums[i]==nums[i-1] && !used[i-1] → 不选 | 排序 |
共同本质：排序让相同值相邻，然后保证同一层里相同值只允许走第一个 。
4.3 最难的一问：去重后，[1,2,2] 怎么生成？
这是我当时最大的困惑：既然去重拦相同值，那包含两个 2 的子集 [1,2,2] 还出得来吗？
答案是：去重拦的是”同层横向”，不拦”同枝纵向” 。把 [1,2,2]（记两个 2 为 2a、2b）的 8 条路径全列出来：
| 路径 | 结果 | 判定 |
|---|---|---|
| 要1 → 要2a → 要2b | [1,2,2] | ✓ 保留 |
| 要1 → 要2a → 不要2b | [1,2] | ✓ 保留（[1,2] 的唯一 生成路径） |
| 要1 → 不要2a → 要2b | [1,2] | ✗ 剪掉 |
| 要1 → 不要2a → 不要2b | [1] | ✓ 保留 |
| 不要1 → 要2a → 要2b | [2,2] | ✓ 保留 |
| 不要1 → 要2a → 不要2b | [2] | ✓ 保留 |
| 不要1 → 不要2a → 要2b | [2] | ✗ 剪掉 |
| 不要1 → 不要2a → 不要2b | [] | ✓ 保留 |
剪掉 2 条，剩 6 个恰好是全部去重子集。画成树：
要 1
不要 1
要 2a
不要 2a
要 2b（同枝）
不要 2b
要 2b
不要 2b
要 2a
不要 2a
要 2b（同枝）
不要 2b
要 2b
不要 2b
开始
[1]
[]
[1,2]
[1]
[1,2,2] ✓
[1,2] ✓
✗ 同层重复，剪掉
[1] ✓
[2]
[]
[2,2] ✓
[2] ✓
✗ 同层重复，剪掉
[] ✓
去重条件里的 !used[i-1] 就是判别同枝还是同层的开关 ：
- 生成
[1,2,2]时：面对 2b，2a 还在 path 里 （used[2a]==true）→ 条件不成立 → 放行 。这是同枝纵向，两个 2 是”都要”的嵌套关系 - 被剪的路径：面对 2b 时，2a 被跳过了 （
used[2a]==false）→ 条件成立 → 拦掉”要 2b”。这是同层横向，”跳过 2a 选 2b”和”选 2a 跳过 2b”产出完全一样
本质一句话：去重后每个子集只剩唯一生成路径，对连续相同值只许取前 k 个，不许跳着取 。[1,2,2] 是”取前 2 个”，[1,2] 是”取前 1 个”，[1] 是”取前 0 个”——全合法；被禁止的只有”取后面的不取前面的”。
4.4 识别信号
看到题面”可能含重复元素 “或”解不能重复 “，第一反应就是上一节那张三题表。
5. 翻车五：范式识别（LC139 陷阱）
单词拆分（LC139），我按回溯建模（“从字典里选词/切段”）。建模本身不算错，但这题根本不该用纯回溯 ——会超时（超时的完整现场在下一篇）。
关键洞察：s 长度到 300，决策树里同一个 start 会被海量重复到达 ——不同路径切到同一个位置，然后从那里重新枚举拆法。而”从 start 开始能否拆完”的答案是确定的，与怎么到达无关 ——这就是无后效性，是 DP 的入场券。
一个杀手级对照，一字之差范式切换：
- 139 单词拆分 ：“能否拆分” → 只要可行性 → DP
- 140 单词拆分 II ：“返回所有拆分方案” → 要枚举 → 回溯 （方案数指数级，DP 折叠的状态存不下每个方案的样子）
识别口诀：只要”能不能/多少种/最优值”用 DP，要”方案/所有”才回溯 。再补一个隐藏信号：n ≤ 20 左右暗示暴力搜索可接受 （答案空间 2^n / n! / C(n,k) 级），n ≥ 10^4 基本和回溯无缘。
| 问法 | 范式 |
|---|---|
| 返回所有 方案 | 回溯 |
| 只要”能不能” | DP（或记忆化回溯） |
| 求最 值 | DP / 贪心 |
| 求方案数量 | DP / 组合数学 |
6. 第一次毕业验收：LC842 将数组拆分成斐波那契序列
用一道综合题验收第一段学习。输入数字字符串，把它拆成斐波那契式序列（每项 = 前两项之和），返回拆出的序列。
设计四件套：
要素| 设计
—|—
决策| 下一段切几位（切割类，1~10 位防溢出）
状态| start（切到哪）+ path（已切出的数，只需看最后两个）
合法性剪枝①| 前导零："0" 合法，"01" 非法——用 break ：0 开头且长度 >1，更长的段也全非法，整层不用再试
合法性剪枝②| 前两层自由切 （无和约束），第三段起切出的值必须 == path 最后两个之和
终止| 切完整串且至少 3 个数
短路| 存在性搜索：找到就返回，且不还原 ——path 保持完整直接当答案上浮
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
func splitIntoFibonacci(num string) []int {
n := len(num)
// 返回 nil 表示失败；成功返回完整方案
var backtrack func(start int, path []int) []int
backtrack = func(start int, path []int) []int {
// 判终：切完整串，至少 3 个数
if start == n {
if len(path) >= 3 {
return append([]int{}, path...) // 拷贝收集
}
return nil
}
// 决策：下一段切 1~10 位
for length := 1; length <= 10 && start+length <= n; length++ {
seg := num[start : start+length]
// 合法性剪枝①：前导零（break，更长的也非法）
if len(seg) > 1 && seg[0] == '0' {
break
}
val, _ := strconv.ParseInt(seg, 10, 64)
// 合法性剪枝②：第三段起，必须等于前两段之和
if len(path) >= 2 && val != int64(path[len(path)-1]+path[len(path)-2]) {
continue
}
// 做选择
path = append(path, int(val))
if ans := backtrack(start+length, path); ans != nil {
return ans // 短路：不还原，带着答案直接上浮
}
// 还原
path = path[:len(path)-1]
}
return nil
}
return backtrack(0, []int{})
}
两个值得看两遍的细节：前导零的 break （一段 0 开头就整层死刑）和短路时不还原 （return ans 跳过了弹出，path 完整地就是答案）。
到这里我以为毕业了。事实证明，这只是下半场的开始——接下来三记重锤，锤出了比前五次更值钱的东西。
总结
上半场的学习轨迹：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
IP 题（照着模板写对）
↓
括号题翻车（决策粒度过粗：一步塞一块）
↓
全排列踩出切片引用的坑（收集必须拷贝）
↓
"要不要"三次误用（47/17/40）
↓
去重三连漏（47 → 40 → 90 同一考点）
↓
139 范式陷阱（该用 DP 的题硬上回溯）
↓
842 毕业验收（切割 + 双剪枝 + 短路收集）
上半场的坑集中在两件事：决策怎么设计 （粒度过粗、模型错配——五坑里三个是它的变体）和重复怎么消灭 （去重三连漏）。两个主题分别指向回溯的两条命脉：模板里的”选择列表”和”同层只走第一个”。
自以为毕业的下一个小时，139 的超时现场（417 万次调用）就把我打回了原形——那三记重锤，在下一篇。
参考资料
- LeetCode 22. 括号生成
- LeetCode 46. 全排列
- LeetCode 47. 全排列 II
- LeetCode 17. 电话号码的字母组合
- LeetCode 40. 组合总和 II
- LeetCode 90. 子集 II
- LeetCode 139. 单词拆分
- LeetCode 842. 将数组拆分成斐波那契序列
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。