LeetCode Hot 100 第17题“电话号码的字母组合”一道标着medium的递归回溯入门题。我很早就刷过这题但最近带几个准备秋招的学弟重新过一遍时发现很多人对回溯的理解都卡在这道题上代码看着很简单照着敲一遍也能AC但改个输入就懵被追问“为什么撤销操作”的时候又说不清楚。所以今天专门写一篇把题目思路、代码实现、复杂度推导、常见坑一次讲透。不管你是刚接触回溯的初学者还是刷了好几轮想查漏补缺的老手这篇都值得花二十分钟耐心看完然后合上题解自己手写一遍收获会比你想象中大得多。1. 这题到底在考什么读懂题意才算开始1.1 题面解读与映射关系的建立题目本身很好理解给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。数字到字母的映射和电话九宫格输入法一致2 对应 abc3 对应 def4 对应 ghi5 对应 jkl6 对应 mno7 对应 pqrs8 对应 tuv9 对应 wxyz。比如输入 23输出就是 [ad,ae,af,bd,be,bf,cd,ce,cf]。这个结果集是怎么来的2 提供 a、b、c 三个字母3 提供 d、e、f 三个字母两组字母做笛卡尔积3 乘 3 等于 9 个组合。这个乘法原理是整个题目最底层的数学本质搞懂它你就明白为什么答案数量是确定的。映射关系建议直接用数组存下标天然对应数字比 HashMap 写起来更干净。数组的第 0 位和第 1 位留空因为题目输入范围是 2-9。这里的工程化小细节是用digits.charAt(index) - 0把字符数字转成整数下标省去 Character.getNumericValue 的冗长写法。很多新手喜欢在循环里写 if-else 判断数字维护起来非常痛苦数组映射是这道题的最优解。1.2 为什么标准的 for 循环没法直接解决这题如果你拿到这道题的第一反应是“这题不是很简单吗几层 for 循环套一下不就出来了”那说明你还没有抓到问题的核心。输入 23 当然可以写两层 for 循环输入 234 写三层输入 2345 写四层那如果是 “23456” 呢循环的层数取决于输入字符串的长度这是动态的程序里没法预知更没法动态生成对应层数的嵌套循环。递归的价值恰好体现在这里递归的深度天然由入参长度决定每一层递归对应处理一个数字递归函数内部只需要写一层 for 循环遍历当前数字映射出来的字符。借助系统调用栈这一层 for 循环就能在每一层被重复执行从而等价替换掉动态层数的嵌套循环。理解这一点你就明白为什么“所有能用嵌套循环解决的问题理论上都能改写成递归”也明白为什么“递归是处理不确定层数嵌套循环的终极武器”。2. 回溯思路破题从递归树到可执行的代码2.1 画出递归树一切就清晰了做回溯题第一件事永远是画递归树代码是树画明白之后自然流淌出来的产物。拿输入 23 举例根节点代表还没开始处理的状态第一层有三个分支分别选择 a、b、c第二层在每一个分支下面又有三个分支分别选择 d、e、f。从根节点走到任意一个叶子节点路径上经过的字符连起来就是一个完整答案。这棵树的深度固定等于 digits.length()每一层可选字符就是当前数字映射出来的字母串。所以整棵树的叶子节点数就是 3 的 N 次方级别的数量如果数字里包含 7 或 9对应位置就是 4 个分支。画完这棵树你会发现回溯的本质就是深度优先遍历这棵多叉树从根出发一条路走到底记录答案然后退回上一个分岔口换一条路再走直到把所有路径都遍历完。这也是回溯这个名词的直观解释先“回”到上一个状态再“溯”向新路径。好多初学者理解不了回溯和递归的关系其实递归是遍历的手段回溯是遍历到死路或无路可走时恢复现场的动作。画一次树胜过看十遍文字解释。2.2 回溯代码的第一版用字符串返回现场先看一个非常常见、适合入门的写法递归参数直接传 String每次递归生成新字符串。优点是代码极短不需要手动恢复现场因为 String 是不可变对象每次拼接都是生成全新对象传给下一层。class Solution { private static final String[] MAPPING { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; public ListString letterCombinations(String digits) { ListString result new ArrayList(); if (digits null || digits.length() 0) { return result; } backtrack(digits, 0, , result); return result; } private void backtrack(String digits, int index, String combination, ListString result) { if (index digits.length()) { result.add(combination); return; } String letters MAPPING[digits.charAt(index) - 0]; for (int i 0; i letters.length(); i) { backtrack(digits, index 1, combination letters.charAt(i), result); } } }这段代码的递归逻辑非常清晰index 表示当前处理到第几个数字combination 表示从根到当前节点已经拼接好的字符串前缀。当 index 等于字符串长度时说明所有数字都处理完了当前的 combination 就是一个完整答案加入结果集。第 20 行的循环是核心每一个字符对应一个分支递归进入下一层后这个分支探索到底返回时 combination 并没有被修改因为combination letters.charAt(i)创建了新的对象原值没有被破坏。2.3 回溯模板的三板斧选择、递归、撤销字符串版本虽然简单但理解回溯的“状态恢复”精髓还是要看可变对象版本。用 StringBuilder 同样能解决这道题而且更贴近绝大多数回溯题的标准写法。核心就三步做选择、进递归、撤销选择。class Solution { private static final String[] MAPPING { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; public ListString letterCombinations(String digits) { ListString result new ArrayList(); if (digits null || digits.length() 0) { return result; } backtrack(digits, 0, new StringBuilder(), result); return result; } private void backtrack(String digits, int index, StringBuilder path, ListString result) { if (index digits.length()) { result.add(path.toString()); return; } String letters MAPPING[digits.charAt(index) - 0]; for (int i 0; i letters.length(); i) { path.append(letters.charAt(i)); backtrack(digits, index 1, path, result); path.deleteCharAt(path.length() - 1); } } }走一遍 23 的完整流程你就能体会为什么要撤销。第一轮外层循环选了 a进入第二层后依次选了 d、e、f得到 ad、ae、af 三个结果。当第二层的 for 循环全部跑完回到第一层循环体时path 还停留在 a 的状态吗不会因为第二层递归返回前最后一次递归里的 deleteCharAt 已经把路径恢复到了 a。此时外层循环进入下一次迭代append bpath 变成 ab继续向下探索。如果不做 deleteCharAtpath 会像滚雪球一样越滚越长第一轮结束就是 ad下一轮直接变成 ade结果彻底崩掉。这就是“恢复现场”的价值也是回溯算法区别于普通递归的最核心特征。3. 两种实现对比String 拼接与 StringBuilder 谁更快3.1 不可变字符串在递归中的隐藏开销很多人觉得字符串版本代码简洁直接用不就行了但你要知道隐藏在简洁背后的性能代价。每次执行combination letters.charAt(i)JVM 都会在堆上创建一个全新的 String 对象。递归树的节点数是指数级的每个节点都会触发一次字符串拼接拼接本身还要复制字符数组这意味着会产生海量临时对象。在力扣这种数据规模下字符串版本通常也能 AC因为这道题的输入长度上限是 4 个数字最坏情况才 4 的 4 次方 256 个组合性能差异根本体现不出来。但这个习惯一旦带到后续题目里就会出问题比如 LeetCode 39 组合总和、46 全排列这些题的组合数量动不动上万字符串拼接带来的 GC 压力就会明显拖慢运行时间。在面试现场面试官如果追问“你的 String 拼接性能有问题怎么优化”你能立刻说出 StringBuilder 方案这本身就是加分项。3.2 StringBuilder 状态恢复的正确姿势用 StringBuilder 有一个必须严格遵循的纪律递归进入下一层前做了什么修改返回后必须原样撤销。这里的对应关系是 append 对应 deleteCharAt一进一出严格对称。path.append(letters.charAt(i)); // 做选择 backtrack(digits, index 1, path, result); // 递归 path.deleteCharAt(path.length() - 1); // 撤销选择注意 deleteCharAt 的参数是path.length() - 1删除的是最后一个字符也就是当前层刚 append 进去的那个字符。好多初学者会写成path.deleteCharAt(index)这是完全错误的。index 代表的是数字位置而 path 的长度在递归过程中动态变化当前层最后加入的字符永远在末尾。还有一个细节结果集记录时一定要path.toString()拷贝一份新的不可变字符串。如果直接把 StringBuilder 对象 add 进 result由于所有递归层共用同一个 path 对象后面所有修改都会污染之前已经记录的结果最后你会发现 result 里全是同一个最终状态的字符串这个错误极其隐蔽排查起来很费时间。4. 复杂度分析与性能优化这道题到底有没有剪枝空间4.1 时间复杂度推导为什么是 3^m 乘以 4^n聊复杂度之前先把变量定义清楚设输入数字串长度为 N其中出现 7 和 9 的次数为 m那么出现 2、3、4、5、6、8 的次数就是 N - m。7 和 9 各映射 4 个字母其余数字映射 3 个字母。最终答案数量等于每一层分支数的乘积也就是4^m × 3^(N-m)这就是叶子节点的个数。每个答案的生成路径长度是 N将答案写入结果集时需要复制这条路径所以总操作量是路径数乘以路径长度时间复杂度为O(N × 4^m × 3^(N-m))。做最坏情况估算时如果输入的数字全部是 7 或 9那么 m 等于 N时间复杂度退化为O(N × 4^N)。这就是力扣题解区常见答案O(3^m × 4^n)里 m 和 n 的来历很多人直接抄复杂度却说不清 m 和 n 代表的含义面试时很容易被问穿。我建议你在简历项目描述里如果提到这道题一定要能自己推导出这个公式。4.2 空间复杂度与真实面试中的追问不计输出结果集的情况下空间复杂度由两部分组成递归调用栈的最大深度等于数字串长度 NStringBuilder 的最大长度也是 N因此总空间复杂度 O(N)。如果面试官要求把结果集计入空间那就是O(N × 4^m × 3^(N-m))因为要存储这么多条路径每条路径长度为 N。面试官追问优化空间时答案可能会让他意外这道题没有剪枝空间。剪枝的前提是存在不满足条件的路径可以提前终止探索。而这题的所有路径天然满足条件不存在“中间状态已经不合法”的场景所以能做的优化非常有限。一个可行的小优化是提前用数组缓存每个数字对应的字符数组而不是每次递归都调用 toCharArray在数据量大的时候能省掉一点重复转换的开销。另外一个思路是如果题目只问组合数量而不要求列出组合根本不用回溯直接套乘法公式一行代码就能返回结果。但如果是要求输出所有组合回溯就是最优解因为任何算法都必须遍历所有路径不可能跳过任何一条合法路径。5. 踩坑实录我在这道题上交过的学费5.1 空字符串输入的处理这道题的第一个隐藏坑就是输入为空字符串的情况。没有判空处理的代码输入 时会直接进入终止条件index digits.length()此时 combination 是空串于是结果集里会莫名其妙多出一个 但题目明确要求返回空列表 [] 而不是包含空字符串的列表。这个坑在力扣上能坑到大量第一次写回溯的新手因为本地测试时很容易直接用 23 测忽视了空输入这种边界情况。我在实际写业务代码时养成了一个习惯任何递归回溯类方法入口处先做入参合法性校验包括 null 判断和空串判断。这道题的原生 LeetCode 测试用例可能不会传 null但面试官一定会问“如果传 null 会怎样”提前处理好能展现出防御性编程的素养。5.2 递归参数传错导致结果丢失用过全局变量保存中间结果的写法会踩到另一个经典问题。我见过有人这样写在类里声明一个StringBuilder path作为成员变量递归函数里也不传 path直接在方法内部修改这个全局 path。表面上看逻辑没问题结果却会出现答案重复或者答案缺失。原因在于全局变量在整个递归过程共享如果某个分支提前 return 或者出现异常path 的状态可能是脏的下一个分支基于脏状态继续拼装就会产生错误结果。回溯算法的标准做法是把路径状态作为递归参数显式传递或者作为成员变量但保证每次进入递归前状态正确、退出后状态恢复。作为成员变量也完全可以但必须严格遵守“恢复现场”的纪律这比参数传递更容易出错。我的建议是算法题里尽量用参数传递代码可读性更好也不容易被突然插入的提前 return 搞乱状态。5.3 不理解“状态恢复”导致答案重复或缺失这道题最核心的概念就是状态恢复我在实际带人时发现很多人写完代码能过但被问到“为什么要 deleteCharAt”就卡住。如果你也卡在这里可以用一个极端例子帮助理解假设注释掉 deleteCharAt 这一行输入 23 会输出什么第一层选 a第二层选 d结果加 ad然后不删除 d第二层继续选 epath 变成 ade答案变成 ade字符串长度都不对了后面的整个递归全乱套。状态恢复就好比你在纸上用铅笔写字写完一条分叉路径后必须用橡皮擦干净才能在下一条分叉路径上继续写。如果不擦所有路径的字都叠在一起什么也看不清。这个比喻我屡试不爽每次讲完对方都恍然大悟。回溯题的调试技巧也很简单在递归函数第一行打印当前 index 和 path观察 path 的变化是否符合预期一旦发现 path 的长度没有对应上 index说明状态恢复出了问题赶紧检查 deleteCharAt 那行。5.4 面试追问的变体把基础解法吃透之后面试官大概率会出一些变体来测试你的理解深度。比如“输入字符串里如果包含 0 和 1你会怎么处理”这个变体考察的是映射表的完整性0 和 1 没有对应字母需要跳过或者返回空。再比如“返回第 k 个组合是什么不要求列出全部组合”这时候可以边遍历边计数到达第 k 个直接返回不需要完整回溯整棵树。更进阶一点的变体是把数字映射关系改掉比如 2 对应 qyz考察你封装映射表的能力。我面试别人的时候特别喜欢问这道题因为它足够短却能把候选人的递归思维、代码风格、边界处理意识全部暴露出来。真正理解回溯的人拿到变体也能很快调整映射表或循环逻辑只会背题解的人一改映射就露馅。6. 从 Hot 100 第17题看回溯题的通法6.1 回溯通用模板提炼这道题刷透之后一定要做一件重要的事把模板提炼出来形成肌肉记忆。各类回溯题不管表面上多么不同解题骨架高度一致。void backtrack(路径参数, 选择列表, 结果集) { if (满足终止条件) { 结果集.add(路径快照); return; } for (选择 : 本层可选列表) { 做选择; backtrack(更新后的参数); 撤销选择; } }区别只在于三个问题的答案不同路径是什么、选择列表怎么定义、终止条件怎么判断。电话号码这道题路径是当前拼接的字母串选择列表是当前数字映射出的字母串终止条件是所有数字都处理完。到了 46 全排列路径是已选数字的排列选择列表变成了还没用过的数字需要用 visited 数组标记终止条件是排列长度等于数组长度。套同一个模板改三个细节就能解一大批题。6.2 配套练习清单与进阶路线建议按照下面的顺序刷题每一道都在上一道基础上增加一点复杂度LeetCode 39 组合总和目标值剪枝理解剪枝对性能的巨大提升LeetCode 46 全排列引入 visited 标记数组掌握“可选列表随路径动态变化”的处理方式LeetCode 78 子集理解“每个节点都记录结果”和“叶子节点记录结果”的区别LeetCode 90 子集 II排序去重掌握同一层去重的经典技巧LeetCode 79 单词搜索二维平面的回溯状态恢复的对象变成网格位置的访问标记LeetCode 51 N 皇后约束条件更复杂每一层要判断是否合法是回溯的综合应用这道题在 Hot 100 里排第 17但实际难度曲线很平缓比很多 medium 的图论题、动态规划题友好得多。它最大的价值是作为回溯专题的起点把这道题的思想摸透后续那些带剪枝、带去重、带多约束的题目才有信心啃下来。7. 最后再说点实战体会我个人刷这道题前后用了三遍才真正理解回溯。第一遍是直接看题解抄了一遍过了但合上代码啥也写不出来。第二遍把递归树画在草稿纸上对着树重新写了一遍终于搞明白了 for 循环和递归的关系。第三遍是在面试模拟时被问到 String 和 StringBuilder 的区别才彻底弄懂状态恢复和性能开销的问题。所以如果你刚接触这道题我建议你拿到题目先别急着写代码先在纸上画递归树画出 23 的完整树形结构再用自己画的树去对答案。等你能不看任何参考写出 StringBuilder 版本并正确解释每一步之后再往前推进到组合总和和全排列。这个流程我验证过很多次是我觉得学习回溯最高效的路径。这道题本身不难但它是后面一系列 backtracking 题目的基石值得多花一点时间把它吃透。
