企业官网建设流程全解析

LeetCode Hot 100 第17题“电话号码的字母组合”，一道标着medium的递归回溯入门题。我很早就刷过这题，但最近带几个准备秋招的学弟重新过一遍时发现，很多人对回溯的理解都卡在这道题上：代码看着很简单，照着敲一遍也能AC，但改个输入就懵，被追问“为什么撤销操作”的时候又说不清楚。所以今天专门写一篇，把题目思路、代码实现、复杂度推导、常见坑一次讲透。不管你是刚接触回溯的初学者，还是刷了好几轮想查漏补缺的老手，这篇都值得花二十分钟耐心看完，然后合上题解自己手写一遍，收获会比你想象中大得多。

1. 这题到底在考什么：读懂题意才算开始

1.1 题面解读与映射关系的建立

题目本身很好理解：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。数字到字母的映射和电话九宫格输入法一致，2 对应 abc，3 对应 def，4 对应 ghi，5 对应 jkl，6 对应 mno，7 对应 pqrs，8 对应 tuv，9 对应 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 List<String> letterCombinations(String digits) { List<String> 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, List<String> 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 List<String> letterCombinations(String digits) { List<String> 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, List<String> 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 'b'，path 变成 "ab"，继续向下探索。如果不做 deleteCharAt，path 会像滚雪球一样越滚越长，第一轮结束就是 "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 空间复杂度与真实面试中的追问

不计输出结果集的情况下，空间复杂度由两部分组成：递归调用栈的最大深度等于数字串长度 N，StringBuilder 的最大长度也是 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，第二层继续选 e，path 变成 "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 题目的基石，值得多花一点时间把它吃透。