企业官网建设流程全解析

这个题名一看就是LeetCode第17题，电话号码的字母组合。我在面试刷题阶段，至少把这个题写了三遍：第一遍对着题解抄，第二遍自己默写，第三遍给别人讲。每一遍的理解都不一样，所以这篇想把回溯到底是怎么一回事彻底讲明白。

题目本身不复杂：给定一个只包含数字2到9的字符串，返回所有它能表示的字母组合。比如输入“23”，输出就是ad、ae、af、bd、be、bf、cd、ce、cf这9个组合。但如果你以为这只是一道简单题，那就错了。它是回溯算法最经典的入门题，几乎所有组合类问题——全排列、组合总和、子集、括号生成——都能在这道题上找到影子。理解这题，后面刷题会顺很多。

这篇我会从题目解读、回溯原理、完整代码、复杂度分析、常见坑点五个角度展开，用我实际写代码的视角来讲，不搞教科书式说教。适合刚接触算法、想系统理解回溯的读者，也适合准备面试想快速温习的兄弟。

1. 看懂题意与核心解题思路

1.1 题目到底在问什么

先看题目的具体描述。给定一个仅包含数字2-9的字符串digits，返回所有它能表示的字母组合，答案可以按任意顺序返回。数字到字母的映射关系，就是老式电话按键上标的那些字母：

注意，数字1和0在按键上没有对应字母，所以题目输入里直接排除了这两个，省去了不少边界处理。

举个例子，输入“23”，数字2对应abc三个字母，数字3对应def三个字母。把两组字母做笛卡尔积，就得到3乘3等于9种组合：ad、ae、af、bd、be、bf、cd、ce、cf。如果输入变成“234”，那就是3乘3乘3等于27种组合。

这里有个容易搞混的点：输出的是组合，不是排列。也就是说，数字2的字母永远在第一位，数字3的字母永远在第二位，位置顺序由输入字符串的数字顺序决定。这一点很关键，它决定了我们后面回溯时不用做“去重”或者“交换位置”这类操作。

另外一个常见的疑问是：为什么输出结果的顺序不受限制？因为LeetCode判定时用的是集合比较，只要内容一致，顺序无所谓。但在实际写递归时，结果顺序天然就是你遍历字母的顺序，所以不操心这个。

1.2 为什么不能写多层for循环

很多第一次做这题的兄弟，第一个念头是：既然数字的位数是固定的，那就写几层for循环呗，比如两位数就写两层，三位数就写三层。

听着挺对，但问题来了。digits的长度是不固定的，可能是“2”，也可能是“2345”。你没法提前知道要写多少层for。就算你硬写，代码也会变成一坨巨型嵌套，根本没法维护。

我在刚开始学的时候，也尝试过用动态拼for循环的方式去解，写完自己都看不懂。后来才明白，这种“循环层数不确定”的枚举问题，正确的解法是递归，也就是回溯算法的核心思想。

顺便说一个生活化的类比。假设你要搭配一周七天的穿搭，每天从几件上衣里选一件。如果固定是7天，你可以写7层循环把每一天都枚举一遍。但如果说“这周要出门的天数不确定，可能3天也可能5天”，循环就没法写死了。这时候你只需要一个递归函数：今天从候选上衣里挑一件，然后进入明天；明天挑完，再退回今天，换一件试试。

回溯就是在做这件事——用递归来模拟“不知道多少层”的循环，同时用撤销操作来保证每一条路径都是独立的。

1.3 映射表怎么建最顺手

建数字到字母的映射表，这道题的第一步。最常见的做法是哈希表（字典）。我用的是字符串类型的字典，键是数字字符，值是字母字符串：

phone = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" }

有人会问，为什么不用数组下标代替字典键？用数组当然也行，比如index 2存放“abc”，index 3存放“def”，反正0和1的空着。不少题解就是这么写的。但我在面试里更推荐字典写法，因为一眼能看出数字和字母的对应关系，不用额外解释数组下标偏移的问题。代码是写给人看的，可读性很重要。

如果你用C++，可以用 unordered_map<char, string>；用Java，可以用 Map<Character, String> 配合 Map.of 来初始化。思路完全一样，选自己熟悉的语言把字典建好就行。

2. 回溯算法的核心原理

2.1 把求解过程看成递归树

很多教材一上来就讲回溯是“深度优先搜索的一种形式”，然后把“决策树”“路径”“选择列表”这些术语甩出来，初学者直接懵。我换一个方式讲。

回到“23”这个例子。我们从空字符串开始，处理第一个数字2，有a、b、c三个分支。选a之后，处理第二个数字3，又有d、e、f三个分支。整个过程就是一棵三层的树：

• 根节点：空路径
• 第一层：选a，或者选b，或者选c
• 第二层：在a下面选d/e/f，在b下面选d/e/f，在c下面选d/e/f
• 叶子节点：ad、ae、af、bd、be、bf、cd、ce、cf

可以把这个过程画成一张树状图，每个叶子节点就是一个答案。回溯算法要做的，就是从根节点出发，沿着这棵树做深度优先遍历，走到叶子节点时记录答案，然后返回上一层节点，换一条路继续走。

为什么叫“回溯”？因为当你处理完一个数字的所有分支后，需要回到上一层，把上一个数字的选择换掉。这个“往回退”的动作，就是回溯。它是递归的自然结果——递归函数返回时，状态会自动回到上一层的样子，前提是你得手动把当前这层对路径的修改撤销干净。

2.2 三个关键动作：选择、递归、撤销

理解了递归树，代码骨架就出来了。核心回溯函数接收一个参数index，表示当前要处理digits中的第几个数字。函数的逻辑可以分成三步：

第一步，如果index已经等于digits的长度，说明所有数字都处理完了，这时候path里的内容就是一个完整组合，把它加入结果集，然后返回。

第二步，取出digits[index]对应的字母串，遍历这个字符串里的每个字母。

第三步，对于每个字母，先把字母追加到path末尾，然后递归调用backtrack(index+1)，等递归返回后，再把刚才追加的字母从path末尾删除。

这里最容易被忽略的，就是第三步里的“删除”。有些初学者会想，为什么每次递归完还要删掉末尾字母？因为path在递归过程中是共享的。假设你处理完“a”开头的三个组合ad、ae、af，如果不清空path，那么path里会残留“a”，等到处理b时，path开头就多了一个a，组合就全乱了。所以我每次递归结束，都要把当前层加进去的字母弹出来，保证path在不同分支之间互不污染。

这个“选择-递归-撤销”的三步套路，你会在之后的组合总和、全排列、子集等题里反复看到。可以把它当成一个固定模板来记，但更重要的是理解为什么撤销，因为面试官最常追问的就是这一步。

2.3 终止条件与结果收集时机

回溯递归最容易写错的地方，是结果收集的时机。

在这个题目里，终止条件是index == len(digits)，也就是所有数字都被分配了一个字母。注意，这个条件是放在backtrack函数的最开头判断的。只有在这个条件下，我们才把path转换成字符串并加入res。

这里有几个细节值得多说一句。第一，res.append的时候，path可能是一个列表或者可变数组，不能直接把path本身放进去，因为后续的修改会改变已经存进res的内容。Python里要用"".join(path)生成一个新字符串，JavaScript里用path.join("")。第二，终止条件一定是在“处理当前数字”之前判断，而不是处理之后。如果你写反了，要么少收集结果，要么数组越界。说白了，当index指向digits末尾之后，说明没有数字可处理了，此时path已经构造完毕，正是收集结果的时机。

另外，空输入的情况要特殊处理。如果digits为空字符串，理论上我们的回溯函数会直接把空path当成一个结果收集进去，返回[""]。但题目要求的是空输入返回[]。所以要么在进入递归前加一个if not digits: return []，要么在终止条件里额外判断。我更推荐前者，因为语义更清晰。

3. 完整代码实现与逐行拆解

3.1 Python版本

先给出Python的完整实现，这是我最常用的写法：

class Solution: def letterCombinations(self, digits: str) -> list[str]: if not digits: return [] phone = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } res = [] path = [] def backtrack(index: int): if index == len(digits): res.append("".join(path)) return letters = phone[digits[index]] for ch in letters: path.append(ch) backtrack(index + 1) path.pop() backtrack(0) return res

代码不长，但每一行都值得掰开讲。

if not digits: return []是防御性代码，处理空输入。phone字典是映射表。res存最终结果，path是当前递归路径上已经选择的字母。

backtrack是核心递归函数。第4行到第6行是终止条件，index走到头就把path拼成字符串存进res。第8行取出当前数字对应的所有候选字母。第9到第11行是主体循环：每遍历一个候选字母，先加入path，再递归处理下一个数字，递归回来后用path.pop()撤销这一步的选择。

很多初学者会疑惑，为什么backtrack定义在letterCombinations方法里，而且可以直接修改res和path？这是Python闭包的特性，内部函数可以访问外部函数的变量。写成内部函数的好处是不用把res和path作为参数来回传递，代码更干净。如果你把backtrack写成类里的独立方法，那就要通过self.res、self.path来引用，或者把它们作为参数传进去，反而麻烦。

3.2 JavaScript版本

JavaScript的写法跟Python几乎一一对应，顺手给出：

var letterCombinations = function(digits) { if (!digits.length) return []; const phone = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" }; const res = []; const path = []; const backtrack = (index) => { if (index === digits.length) { res.push(path.join("")); return; } const letters = phone[digits[index]]; for (const ch of letters) { path.push(ch); backtrack(index + 1); path.pop(); } }; backtrack(0); return res; };

JavaScript里唯一要注意的点，是res.push(path.join(""))这一句。如果你写成res.push(path)，那么所有结果都会引用同一个数组对象，最后输出的全是同一个值，这是新手最容易踩的坑。path.join("")生成了一个新字符串，才算是把当前状态“快照”下来了。

闭包特性在JavaScript里同样成立，所以backtrack也可以直接访问外层的res和path，不需要额外传参。

3.3 path的另一种写法：传字符串而不是数组

除了用数组加append/pop之外，还有一种很常见的写法是直接用字符串拼接：

def backtrack(index, cur): if index == len(digits): res.append(cur) return for ch in phone[digits[index]]: backtrack(index + 1, cur + ch)

这种写法更简洁，因为cur + ch创建了一个新字符串，天然不需要手动撤销，递归里每一层都有自己的拷贝。很多题解和官方答案就是这么写的。

但我个人推荐在实际面试中优先使用数组加撤销的版本。原因有两点：第一，字符串拼接在循环中会创建大量新对象，虽然在这个题目的规模下性能差异可以忽略，但习惯一旦养成，以后做更复杂的回溯题时，数组版本的状态管理更直观；第二，面试官追问“回溯的精髓是什么”时，你能靠数组版本清晰讲出“做选择、递归、撤销”三步，而字符串版本因为不需要撤销，反而讲不清回溯的味道。

当然，两种都能跑，你只要能讲清楚原理，用哪个都行。我一般是在白板上写数组版本，时间宽裕时再提一句“也可以用字符串拼接实现”，显得你对这个解法理解更深入。

4. 复杂度分析与迭代版本

4.1 时间复杂度到底怎么算

回溯题的时间复杂度分析，是面试里一个高频追问点。这道题不能只说“指数级”，要说得更准确。

设digits长度为n，其中有m个数字对应3个字母（2、3、4、5、6、8），有k个数字对应4个字母（7、9），那么m + k = n。所有可能的组合数量是3的m次方乘4的k次方，也就是3^m * 4^k。

每个组合在收集时，需要把path转换成字符串，这一步的代价是O(n)。所以总时间复杂度是O(3^m * 4^k * n)。如果你只想要一个粗略上界，可以用O(4^n * n)，因为4是单个数字的最大分支数，这个上界虽然不够精确，但能表达“随输入长度指数爆炸”的意思。

空间复杂度上，递归栈的最大深度是n，path数组的长度也是n，所以不算res那块输出空间的话，额外空间是O(n)。如果把结果集也算进去，那总空间就是O(3^m * 4^k * n)，因为res里存的每个字符串长度都是n。

很多同学会把时间复杂度和空间复杂度搞混，这里记住一个关键点：空间复杂度看递归深度，时间复杂度看节点总数乘上每个节点的操作成本，就能基本上不出错。

4.2 用队列实现的BFS版本

说完了递归，再提供一个完全不用递归的BFS写法。思路是：用一个队列保存中间状态，依次处理digits里的每个数字，每处理一个，就把当前队列里的所有前缀和该数字的所有字母做一次拼接，生成新一轮的队列内容。

直接看代码：

def letterCombinations(self, digits: str) -> list[str]: if not digits: return [] phone = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } res = [""] for d in digits: res = [prefix + ch for prefix in res for ch in phone[d]] return res

这个写法只有四五行，非常漂亮。初始时res里有一个空字符串，代表还没处理任何一个数字。遍历digits里的每个数字d，用两层列表推导式，把当前所有前缀和d对应的所有字母做笛卡尔积，得到新的前缀列表。循环结束，res里就是所有完整组合。

比如输入“23”，初始res是[""]。处理2之后，res变成["a", "b", "c"]。处理3之后，res变成["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

这个方案从本质上讲是广度优先遍历，它和递归版的深度优先遍历是等价的，只是遍历顺序不同。如果你在面试里先写了递归版，可以在最后提一句还能用队列实现，一般会是个加分项，因为说明你不只是背模板，而是真的理解不同遍历方式的关系。

4.3 递归和迭代怎么选

递归版和BFS版没有绝对的优劣。递归版更贴近回溯的标准模板，适合用来讲清楚“选择、递归、撤销”的思维过程；BFS版代码更短，但理解起来对新人稍微绕一点。

从性能角度看，两种方案的复杂度是一样的，区别只是递归有函数调用栈的额外开销，BFS有创建新列表的开销。在这个数据规模下，根本感知不到差异。真正重要的是你能否用自己选择的方式，把思路讲清楚。

我个人建议：主推递归版，因为绝大多数回溯题（组合、排列、子集）都是递归树形态，递归版能直接套用到后续的题目上。BFS版更适合作为“额外思路”在面试中展示，而不是作为主答案。

5. 常见问题、易错点与刷题心得

5.1 空输入和单数字输入的坑

空输入返回[]还是[""]，这个细节我已经在前面提过了，但还是要强调，因为真的有很多人在LeetCode上栽在这一点。原因在于，回溯终止条件是index == len(digits)，当digits为空时，index一开始就等于0，也等于len(digits)，于是会把空字符串当作结果收集起来。这也提醒我们：任何回溯题，都要先想清楚“空输入”这个边界。

单数字输入相对简单，比如输入"2"，直接返回["a", "b", "c"]。只要递归框架正确，这个case不会出问题。但有些初学者会把初始res写成[""]然后忘了判断空输入，结果单数字倒是能跑通，空输入就挂了。所以测试的时候，至少要测三个case：空串、单数字、多数字。

5.2 为什么这里不需要startIndex参数

组合类题里有一个常见的套路参数startIndex，用来限制后续选择的范围，防止出现重复组合。比如在组合总和问题里，选了1之后就不能再选1，所以下一层递归要从下一个位置开始。

但电话号码这题完全不需要startIndex。原因是每个数字对应的位置是固定的，你处理完第0个数字，下一次永远处理第1个数字，不存在“跳过某些位置”的选择。每一层的选择范围，只由当前数字对应的字母集合决定，与之前选了哪个字母无关。这也是为什么backtrack函数只需要index一个参数，而不需要startIndex或者visited数组。

如果你发现自己在做这题时加了startIndex，大概率是混淆了“组合”和“排列”的套路。这里先给大家提个醒：死记模板会出问题，理解每道题的选择空间才是最关键的。

5.3 从这题延伸出去的刷题路线

电话号码的字母组合之所以被称为回溯入门题，是因为它剔除了很多干扰因素：没有重复元素、没有排序要求、没有去重逻辑、不需要剪枝，只需要最纯粹的递归枚举。

做熟这题之后，建议按这个顺序往下刷：

第一站是全排列问题。它跟这题的区别在于，每个位置能选的数字不再是固定的几个，而是所有未使用过的数字，所以需要引入visited数组或者used数组来标记哪些元素已经用过了。

第二站是组合总和。它引入了一个startIndex来防止重复组合，同时多了“剪枝”思想——当前和已经超过目标值时提前返回。

第三站是子集问题。它和组合问题很相似，唯一的区别是收集结果的时机变了：子集问题在递归的每一层都要收集当前路径，而组合问题只在叶子节点收集。

第四站是括号生成。它表面上是字符串问题，实质是带约束的回溯：每一步可以加左括号或者右括号，但右括号数量不能超过左括号，这就是剪枝。

沿着这条路线刷下来，你会慢慢发现，所有回溯题都在反复用同一套“选择、递归、撤销”框架，只是在不同场景下加了不同的约束条件。而这一切的起点，就是电话号码的字母组合这道最纯粹的题。

我后来在带新人刷题时，也一直用这题作为回溯的破冰题。只要把这题的每个细节讲透，后面再讲全排列、组合总和，对方接受起来会快很多。如果你正在准备面试，这题值得花一个小时好好琢磨，把递归树亲手画一遍，把代码默写三遍，把空输入、单数字、多数字的case都自己跑一遍，比刷十道没消化的题有用得多。