这个题名一看就是LeetCode第17题电话号码的字母组合。我在面试刷题阶段至少把这个题写了三遍第一遍对着题解抄第二遍自己默写第三遍给别人讲。每一遍的理解都不一样所以这篇想把回溯到底是怎么一回事彻底讲明白。题目本身不复杂给定一个只包含数字2到9的字符串返回所有它能表示的字母组合。比如输入“23”输出就是ad、ae、af、bd、be、bf、cd、ce、cf这9个组合。但如果你以为这只是一道简单题那就错了。它是回溯算法最经典的入门题几乎所有组合类问题——全排列、组合总和、子集、括号生成——都能在这道题上找到影子。理解这题后面刷题会顺很多。这篇我会从题目解读、回溯原理、完整代码、复杂度分析、常见坑点五个角度展开用我实际写代码的视角来讲不搞教科书式说教。适合刚接触算法、想系统理解回溯的读者也适合准备面试想快速温习的兄弟。1. 看懂题意与核心解题思路1.1 题目到底在问什么先看题目的具体描述。给定一个仅包含数字2-9的字符串digits返回所有它能表示的字母组合答案可以按任意顺序返回。数字到字母的映射关系就是老式电话按键上标的那些字母数字对应字母2abc3def4ghi5jkl6mno7pqrs8tuv9wxyz注意数字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_mapchar, string用Java可以用 MapCharacter, 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(index1)等递归返回后再把刚才追加的字母从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是单个数字的最大分支数这个上界虽然不够精确但能表达“随输入长度指数爆炸”的意思。空间复杂度上递归栈的最大深度是npath数组的长度也是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都自己跑一遍比刷十道没消化的题有用得多。