如果你最近在刷 LeetCode 的 hot100 系列大概率会卡在中间这一段。不是题目多难而是题型突然变得很“杂”——前面还在搞数组、哈希表到了 NO.77~80 这四题一下就把回溯、DFS、双指针全混在一起了。我自己当初刷到这一段的时候第一反应是“这四题放一起是不是故意的”后来刷完才发现它们确实是一个刻意安排的组合两题回溯、一题搜索、一题数组技巧刚好能把中级算法里最常考的几类思路串起来。这篇文章就围绕 hot100 里 NO.77~80 这四道题展开按我自己的刷题顺序和复盘笔记来写。不管你是刚开始刷 hot100 的新手还是已经刷过几十题想回头夯实基础的人这四题都值得认真过一遍。尤其是 77 和 78它们几乎是所有回溯题的地基79 是 DFS 在二维网格上的经典应用80 看起来最简单但双指针的边界处理非常容易写错。我会把每道题的思路、代码、复杂度、易错点全部拆开讲清楚最后再汇总一个横向对比和排查清单帮你把这四题彻底吃透。1. 整体设计与思路拆解1.1 为什么这四题要放在一起刷先看这四题分别是什么组合给定 n 和 k返回 1..n 中所有可能的 k 个数的组合。子集给定一个不含重复元素的整数数组 nums返回所有可能的子集。单词搜索给定一个二维网格和一个单词判断单词是否存在于网格中。删除有序数组中的重复项 II给定一个有序数组原地删除重复出现的元素使每个元素最多出现两次返回删除后数组的新长度。表面上看77 和 78 都是“枚举所有情况”的题目79 是“在网格里走迷宫”80 是“数组原地操作”好像没什么关联。但你实际动手写代码就会发现它们背后是一条非常清晰的能力递进链路77 和 78 是回溯/DFS 的入门题核心在于“选或不选”和“顺序无关”这两个概念。79 是把回溯从一维数组扩展到二维网格核心在于“方向选择”和“状态恢复”。80 则完全换了个赛道考的是双指针的原地覆盖技巧不涉及递归。如果你按这个顺序刷就能很自然地体会到回溯是一种“结构化的暴力枚举”DFS 是它的底层执行方式而双指针则是另一种更轻量的数组处理思路。这种“同中有异、异中有同”的编排恰好是 hot100 这个系列最有价值的地方——它不是让你死记题目而是让你在题目之间建立联系。我个人强烈建议这四题不要跳着刷按 77 → 78 → 79 → 80 的顺序来因为 77 的“组合”和 78 的“子集”几乎是同一套模板先刷 77 再刷 78你会觉得 78 简单一半而 79 又是在 77/78 的回溯基础上多了一个“网格方向”的维度难度是自然递进的。1.2 刷这四题需要提前掌握哪些基础先说结论只要你会写递归、知道什么是栈就够用了。但有几个概念最好提前搞清楚否则后面容易懵。第一个是“回溯”到底是什么。用一句话概括回溯就是“走不通就回头”它在递归过程中尝试所有可能路径一旦当前路径不可能得到合法答案就撤销上一步的选择回到上一个状态继续尝试。你可以把它想象成走迷宫——你每到一个路口先选一条路走走到死胡同就退回上一个路口换一条路。第二个是“剪枝”。很多回溯题的时间复杂度天差地别区别就在剪枝。比如 77 组合里如果当前已经选的数字加上剩余可选数字都不够 k 个那这整条分支就已经废了可以直接 return。这就是剪枝。第三个是“原地操作”。这个主要是 80 题的概念要求你不能新建数组只能在原数组上修改最后返回新长度。面试里经常遇到因为你不能总是靠“生成新数组”来解决问题必须考虑空间复杂度。如果你之前没接触过递归建议先找两道简单的递归题练手比如计算斐波那契数列、反转链表。不然直接硬啃回溯会很受挫。我见过不少朋友上来就刷 77结果被递归绕晕回头连基础题都不想刷了其实没必要循序渐进反而最快。2. 回溯题核心细节77 组合与 78 子集2.1 从“组合”模板开始理解 start 参数的作用77 组合的题目很简洁给定 n 和 k返回 1 到 n 中所有可能的 k 个数的组合。比如 n4k2结果就是 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。这里最关键的一点是“组合不讲究顺序”[1,2] 和 [2,1] 被视为同一个组合所以你需要用一个 start 参数来规定当前层只能从 start 开始往后选这样就不会出现回头选前面数字的情况。算法通过这个参数天然避免了重复组合的产生不需要哈希集合去重代码也更干净。代码模板如下def combine(n: int, k: int) - List[List[int]]: res [] path [] def backtrack(start): # 剪枝剩余数字不够凑齐 k 个 if len(path) (n - start 1) k: return # 终止条件 if len(path) k: res.append(path[:]) return # 从 start 开始枚举 for i in range(start, n 1): path.append(i) # 做选择 backtrack(i 1) # 递归下一层 path.pop() # 撤销选择 backtrack(1) return res注意几个细节res.append(path[:])而不是res.append(path)因为后续path.pop()会修改同一个列表直接 append 的话最终存进去的全是空列表。这是回溯题里最常见的坑。剪枝条件len(path) (n - start 1) k的意思是当前已经有len(path)个元素而start到n最多还能选n - start 1个元素如果两者之和都小于 k说明这条路无论怎么走都不可能凑够 k 个直接放弃。start 的初始值是 1不是 0因为题目给的是 1~n 的数字。2.2 从组合到子集模板不变只是扩展了终止条件78 子集说的是给定不含重复元素的数组 nums返回所有可能的子集。比如 nums[1,2,3]结果就是 [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。你会发现“子集”其实就是“组合”的一种超集组合是固定 k 个元素子集是所有可能的 k0 到 n。所以解法就是在组合题模板的基础上把“记录结果”的时机从“len(path) k”改成“每次进入递归都记录”也就是每个节点都算一个子集而不是只记录叶子节点。对应代码def subsets(nums: List[int]) - List[List[int]]: res [] path [] def backtrack(start): # 每个前缀都是子集 res.append(path[:]) # 枚举下一个元素 for i in range(start, len(nums)): path.append(nums[i]) backtrack(i 1) path.pop() backtrack(0) return res这题还可以用另一种思路做——对每个元素“选或不选”做递归但那样写出来的代码没有统一模板。我建议你以“for 循环 start 参数”的版本为准因为后面碰到含重复元素的题目时这个模板只需要加一行去重判断扩展性最好。2.3 回溯题的时间复杂度与优化心得77 组合的时间复杂度是 O(C(n,k) * k)因为组合数本身就有 C(n,k) 种每种组合拷贝出来要 O(k)。78 子集的时间复杂度是 O(2^n)因为子集总数是 2^n 个。空间复杂度两者都是 O(n)递归栈的深度。这四题我反复强调模板化是因为 hot100 后面的题目“全排列”“电话号码的字母组合”“括号生成”全都是从这个模板长出来的。你只要把 77 的模板背熟后面遇到新题无非是改三件事递归参数、终止条件、剪枝条件。记住这个规律刷题效率会提升很多。2.4 小心这两个回溯高频坑第一个坑是深拷贝。Python 里列表是引用类型res.append(path)拼的是引用不是值。每次修改 pathres 里已经存进去的内容也会变。务必用path[:]先复制一份。第二个坑是剪枝写错导致超时。组合问题如果不剪枝n20、k10 这种输入直接能把你的递归跑爆炸。剪枝条件要写在递归函数最前面越早越节约。3. DFS 在二维网格上的应用79 单词搜索3.1 这题的难点不在于递归而在于方向处理和状态重置79 单词搜索是最经典的二维网格 DFS 题。给定一个 m×n 的 board 和一个单词 word判断单词是否由网格中相邻单元格内的字母构成同一个单元格不能重复使用。比如 board [[A,B,C,E],[S,F,C,S],[A,D,E,E]]word ABCCED返回 true。路径就是 A → B → C → C → E → D 这样走出来的。这题的难点有三个怎么在二维坐标上做 DFS也就是怎么控制上下左右四个方向。怎么在搜索失败时恢复现场否则会错误标记“已访问”的格子。怎么处理极端情况比如单词长度超过网格总格子数或者只有一个格子的情况。核心思路是从每个坐标出发依次匹配 word 的第一个字符匹配成功后再递归查找四个方向看能否匹配下一个字符。如果四个方向都不行就回溯把当前格子标记清除。3.2 标准 Python 实现附方向数组写法def exist(board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) # 方向数组上、下、左、右 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(i, j, index): # 剪枝当前字符不匹配 if board[i][j] ! word[index]: return False # 最后一个字符匹配成功 if index len(word) - 1: return True # 标记为已访问 temp board[i][j] board[i][j] # for dx, dy in directions: ni, nj i dx, j dy if 0 ni m and 0 nj n and board[ni][nj] ! #: if dfs(ni, nj, index 1): return True # 恢复现场 board[i][j] temp return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这里有几点值得展开说状态恢复是必须的。这里用了临时变量 temp 存原来的字符最后再还原等于把“访问过的格子”标记为特殊字符 #。如果你不恢复一个格子一旦走过就会永远不可访问所有路径都会因为“死路”而失败。方向数组写法的好处是代码简洁、可扩展。如果你以后想改进成“允许斜着走”或者“允许跳格子”只需要改 directions 数组就行。在主函数里先遍历所有坐标每个坐标都作为起点尝试一次。遇到已经找到的情况直接返回 True不需要继续无意义的搜索。3.3 性能优化先做字符频率预检这是很多人容易忽略的优化点。如果 word 里的某些字符在 board 里根本不存在或者数量不足完全可以提前返回 False不用跑完整 DFS。from collections import Counter # 预检board 里每个字符的数量必须不少于 word 中对应字符的数量 board_counter Counter(board[i][j] for i in range(m) for j in range(n)) word_counter Counter(word) if any(board_counter[c] word_counter[c] for c in word_counter): return False这一招在 word 很长、board 很稀疏的时候效果非常明显能把最坏情况的耗时从秒级别降到毫秒级别。我自己实测过在 LeetCode 的用例下这个预检能省掉大量无效搜索。另外还有一个小优化如果 word 的首字符在 board 中出现的次数比末字符多可以尝试把 word 反转后再搜索。这是利用了“从出现次数更少的端点开始搜索分支更少”的原理。不过这个优化属于锦上添花面试时先说出频率预检就够加分了。3.4 79 题的复杂度与易错场景时间复杂度最坏是 O(m * n * 4^len(word))因为每个格子最多有 4 个方向可走。空间复杂度 O(len(word))递归栈深度。易错场景有三个第一个是坐标越界每次递归访问邻居前必须检查边界第二个是重复访问同一个格子一定记得用标记位第三个是 board 只有一个格子时要保证能正确返回结果别让递归去访问不存在的邻居。4. 双指针的“覆盖法”80 删除有序数组中的重复项 II4.1 这题其实是在考你“怎么写得更优雅”的边界处理80 题的要求是给一个有序数组 nums原地删除重复出现的元素使每个元素最多出现两次返回删除后数组的新长度。不能用额外数组空间。比如 nums [1,1,1,2,2,3]处理后长度是 5前五个元素变成 [1,1,2,2,3]。我见过很多人一上来就想着“统计每个元素出现次数然后重建数组”但这样大概率要用到额外数组不符合题目要求。正确解法是用双指针核心套路是慢指针维护“已处理好的数组末尾”快指针遍历整个数组。核心判断条件就是当前元素能不能保留在有序数组的前提下你只需要看它和它前面第二个保留元素是否相同。更具体地说慢指针指向的是“下一个待填充的位置”如果nums[快指针] ! nums[慢指针-2]说明这个元素没有超过两次可以填充到慢指针的位置否则跳过。4.2 代码逐行解说def removeDuplicates(nums: List[int]) - int: if len(nums) 2: return len(nums) slow 2 for fast in range(2, len(nums)): if nums[fast] ! nums[slow - 2]: nums[slow] nums[fast] slow 1 return slow这段代码非常短但信息量很大。我来逐步拆解为什么 slow 从 2 开始因为前两个元素无论如何都会被保留每个元素最多出现两次嘛。slow 是“下一个待填充的位置”初始就指向索引 2。为什么比较nums[fast] ! nums[slow-2]因为数组是有序的如果当前遍历的元素和“已保留区间的倒数第二个位置”相同说明它至少是第三个重复元素必须跳过。如果不同说明它是新出现的元素或者只重复了一次可以保留。整个过程就是“读”和“写”分离。fast 负责读slow 负责写。读到一个合法元素就写到 slow 位置slow 前进一格。最后 slow 的值就是新数组的长度。你可以手动模拟一遍 [1,1,1,2,2,3]初始 slow2fast2nums[2]1nums[0]1相等跳过fast3nums[3]2nums[1]1不相等执行nums[2]2slow3fast4nums[4]2nums[2]2注意这里 nums[2] 刚被覆盖成 2相等跳过fast5nums[5]3nums[3]2不相等执行nums[3]3slow4。最后返回 4前四位变成 [1,1,2,3]符合预期。4.3 双指针模板的可迁移性这个题的最优解思路并不只适用于“每个元素最多出现两次”。如果你把条件改成“每个元素最多出现 k 次”代码几乎不用变只需把slow 2改成slow k把nums[slow - 2]改成nums[slow - k]。def removeDuplicates(nums: List[int], k: int) - int: if len(nums) k: return len(nums) slow k for fast in range(k, len(nums)): if nums[fast] ! nums[slow - k]: nums[slow] nums[fast] slow 1 return slow这就是模板化的价值。你做过的题不一定原封不动地出现在面试里但“覆盖法 双指针”这个套路可以迁移到很多场景比如去除有序数组中的指定元素、移动零、压缩字符串等。4.4 80 题的易错点第一个易错点是忘记处理len(nums) 2的边界情况。如果数组长度就 1 或 2直接返回原长度即可否则nums[slow - 2]会访问到负数索引产生意外结果。第二个易错点是混淆了slow-2和fast-2。这里比较的一定是“已保留区间的倒数第二个”而不是“遍历到当前位置的前两个”因为中间可能夹着很多被删除的重复值。第三个易错点是没理解“原地”的含义如果面试时你新建了列表就算结果对面试官也会追问如何优化空间复杂度。5. 四题横向对比与高频问题排查5.1 题目类型与核心考点一览为了方便你复习我整理了一张对比表题号题目核心算法时间复杂度空间复杂度核心考点77组合回溯O(C(n,k) * k)O(n)start 参数、剪枝78子集回溯O(2^n)O(n)回溯模板扩展79单词搜索DFS / 回溯O(m * n * 4^L)O(L)状态恢复、方向数组80删除有序数组中的重复项 II双指针O(n)O(1)覆盖法、边界处理这张表的用途不是让你背而是帮你建立“看到题先分类”的习惯。你拿到一道新题先问自己这是枚举所有情况回溯/DFS还是在数组上做优化双指针/滑窗分类对了解题方向基本就定了。5.2 刷题过程中常见的报错与排查思路我在刷这四题时以及帮朋友 review 代码时最常遇到下面几类问题结果集为空或少了部分结果。八成是回溯时在“进入递归前”和“递归返回后”少了状态恢复或者 append 时用了原列表引用。排查方法是打印 path 的中间状态看递归过程是否正常。重复结果太多。通常是 77 这类组合题没有用 start 参数导致同一个组合被不同顺序枚举出来。排查方法是检查 start 是否在每次递归时正确递增。79 单词搜索超时。优先加上字符频率预检再考虑方向顺序是否合理。另外检查是否有重复访问同一个格子导致死循环标记位是否及时清除。80 题返回长度不对。用一个小数组走一遍流程把 slow 和 fast 在每个循环里的值打印出来十秒钟就能定位问题。5.3 面试官在这四题上常做的扩展与追问面试官特别喜欢在这几道题上往下追问这是 hot100 刷题者必须提前准备的77 的追问通常是“如果 n 和 k 特别大怎么优化”答案是剪枝也就是我前面写的那个判断条件更进一步可以提“如果要求按字典序输出结果该怎么改”。78 的追问通常是“如果 nums 里有重复元素怎么去重”答案是先排序再在 for 循环中跳过和前一个相同的元素。这是 hot100 中“子集 II”的解法也是在 78 模板上只加几行代码。79 的追问通常是“能不能不用递归做”可以用显式栈模拟 DFS但代码更复杂面试时一般考查对递归的理解写递归是加分项。还会追问“如何找到所有路径而不只是判断是否存在”那就需要收集路径注意收集时机。80 的追问通常是“如果数组不是有序的怎么办”那问题就变成“如何让每个元素最多出现两次”这时可以用哈希表统计次数但空间复杂度就变成 O(n) 了。所以这题的“有序”条件非常关键是双指针解法成立的前提。5.4 复盘技巧这四题刷完应该达到什么效果刷完之后你可以做一个简单的自测不看任何笔记手写 77 和 78 的回溯模板再默写 80 的双指针解法。如果能顺利写出来说明你真的掌握了不是靠看答案混过去的。另外一个很好的复盘方式是把四题放在同一个工程里用一组函数同时实现“组合”“子集”“单词搜索”“去重”这四种能力。我自己在本地就是这么练的相当于一个 mini 算法工具箱后面刷 hot100 其他题目时经常直接复用这里写好的回溯模板和双指针模板省了不少时间。6. 基于这四题的经验总结与实际建议最后分享一些我在刷这四题以及后续刷 hot100 过程中的实际感受希望能对你的学习路径有帮助。第一不要嫌模板枯燥。有些人觉得“背模板”是应试思维我恰恰认为回溯和 DFS 这种算法题型模板就是最小可用骨架。模板帮你把 90% 的机械工作做掉剩下的精力可以集中在“终止条件”“剪枝条件”“状态恢复”这三个变量上。等你熟练之后模板会内化成你自己的思维模型不再是死记硬背。第二每道题都要做“一题多解”的思考。比如 77 组合不仅能递归做还能用迭代法用栈模拟递归78 子集除了回溯还可以用位运算枚举从 0 到 2^n - 1 的每个数字代表一种选择状态80 的双指针方案甚至还能进一步优化成每次移动多个步长。这种横向扩展能帮你把单一知识点编织成知识网面试时灵活度完全不一样。第三代码写完一定要手动走一遍例子。不要急着提交先在纸上或注释里模拟一遍中间变量。因为算法题最容易错的不是思路而是索引和边界。我见过太多人在 80 题上栽跟头就是因为没模拟 slow 和 fast 的移动过程结果返回的长度不对还很困惑。第四在这个阶段刻意控制耗时。这四题分别模拟了 LeetCode 的中等难度我的建议是每道题给自己 30 分钟左右。如果 30 分钟没有思路再看题解看完题解之后合上屏幕自己重新写一遍直到能独立 AC。这样做记忆深度远大于直接抄答案也符合 hot100 刷题“质量大于数量”的原则。我自己的经验是刷完这四题之后再回去看热题 100 里后面的题目比如全排列、电话号码的字母组合、括号生成会觉得亲切很多。因为它们本质上都是从 77/78 的回溯模板长出来的。而 79 题帮你建立的“二维网格 DFS”能力后面在做岛屿类题目、矩阵路径类题目时也会持续复用。至于 80 题的双指针覆盖法更是在“原地操作数组”这个类别里屡试不爽。所以如果你现在正好刷到 hot100 的 NO.77~80安心把这四题啃透它们就是你在算法这条路上一个很扎实的垫脚石。