有一次模拟面试问题正好碰上原题编号17的“电话号码的数字组合”。候选人很快写出了三层循环把输入“23”跑通了面试官接着把输入换成“234567”循环层数没法写死场面一下子就安静下来。这道题在各大刷题平台流传很广看起来只是输出几个字母串实际上它是回溯算法最经典的入门题之一。你不需要先懂排列组合、不需要处理去重和剪枝只要把“递归撤销选择”这一件事弄明白就能轻松拿下。这篇文章我会从为什么不能写死循环讲起把映射表怎么建、递归函数怎么设计、代码怎么落地、边界条件有什么坑、复杂度怎么分析全部过一遍最后再聊聊怎么用这道题打通全排列、子集、组合总和那一类回溯题目。无论你是刚开始刷题的新手还是准备面试想补回溯模板的人都可以直接参考。1. 先想清楚为什么这题不能用写死的循环而要走回溯1.1 题目本身其实很短别被“组合”两个字吓到题目内容一句话就能说清楚给定一个数字字符串比如“23”返回这些数字在电话键盘上能组成的全部字母组合。电话键盘的映射是固定的2对应abc3对应def4对应ghi5对应jkl6对应mno7对应pqrs8对应tuv9对应wxyz。输入“23”的时候第一个数字有a、b、c三种选择第二个数字有d、e、f三种选择组合起来就是ad、ae、af、bd、be、bf、cd、ce、cf一共9个。如果输入是“2”结果就是a、b、c。如果输入是空字符串结果是一个空列表不是包含一个空串的列表。这个边界条件看着简单后面我专门会讲因为真有人在面试时在这里翻车。题名里的“组合”两个字容易吓到人会让人联想到高中的排列组合公式。但这题本质上不是数学组合问题而是一棵多叉树的遍历问题。每个数字是一个树层数字对应的每个字母是一条分支从根走到叶子就得到一条完整的字母组合。理解了这一点后面所有代码逻辑都能对得上。1.2 嵌套循环的致命问题循环层数由输入决定很多人第一反应是用循环暴力枚举。如果输入固定是两位数字那就写两层循环外层遍历第一个数字的字母内层遍历第二个数字的字母。如果固定是三位数字就写三层循环。可问题是输入长度是运行时才知道的可能是1位也可能是4位、10位你不可能事先在代码里写10层循环。我见过有候选人试图用动态生成代码之类的方式绕过这个问题那完全是给自己挖坑。更合理的做法是意识到既然循环层数不固定那就需要用递归来代替循环。递归的每一层调用对应一个数字每递归一层index加1当index走到digits末尾时当前路径就是一个完整答案。这个过程本质上是在遍历一棵树树的高度就是digits的长度每一层的分支数就是当前数字对应的字母数。这里有一个类比很形象你在点一份套餐第一个数字的字母是主食选项第二个数字的字母是配菜选项第三个数字的字母是饮料选项。你需要把每一层选一个出来串成一份完整套餐。写循环相当于你提前知道套餐有几类东西写递归则是“不管有几类我每次处理一类处理完就交给下一层”。1.3 回溯和BFS都能解面试官更想听到哪个这道题其实有两条主流解法。一条是回溯/DFS一条是BFS式的逐层累乘。BFS的写法非常短Python里用列表推导式几行就能写完先让结果集等于[]每读一个数字就把当前结果集中的每个前缀都拼上这个数字对应的所有字母生成新的结果集。这个思路也很清晰相当于一层一层往外扩展。但面试场景里我更推荐你先讲回溯。原因很简单回溯是后面一大类题目的通用解法全排列、子集、组合总和、括号生成都需要同一套思维。面试官问你“为什么用回溯”你可以说因为选择层数不固定并且每一层的选择列表是独立的递归天然适合这种多叉树遍历。你如果只写BFS哪怕代码再短也很难把话题延伸到更复杂的题目上。BFS可以作为回溯讲完之后的补充说一句“这题用BFS也能做代码更短”反而显得你视野宽。2. 动手前先定数据模型映射表、递归参数和递归树2.1 映射表用数组而不是字典理由很朴素第一步是建立数字到字母的映射。两种常见做法一种是哈希表/字典键是字符“2”“3”这种值是“abc”“def”这种另一种是数组下标0到9每个位置放对应的字母串。我强烈建议用数组而且把下标0和1的位置留成空字符串。原因很朴素输入是字符串取每一位数字时可以用digits.charAt(index) - 0直接得到整数下标一次数组访问就拿到字母串代码非常干净。用字典的话你得先取字符再查表功能一样但写起来多一层转换而且面试官追问时你还得解释为什么key用字符不用整数。数组初始化长这样private static final String[] PHONE { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz };等下重点来了PHONE[0]和PHONE[1]必须是空字符串。虽然题目保证输入只含2到9但数组下标必须从0开始占位不然digits.charAt(index) - 0算出来是2的时候你总不能往数组下标0里放“abc”吧。这个占位细节就是数组映射和字典映射的最大区别字典可以只放2到9的键数组必须把0到9十个位置都占满。2.2 递归函数的五个参数每一个都有存在理由接下来定义递归函数。以Java为例我习惯写成这样backtrack(String digits, int index, StringBuilder path, ListString result)你可能发现这里没有传PHONE数组。因为PHONE是成员变量/静态变量递归里直接访问就行不用反复传递。真正必要的参数是四个digits、index、path、result。digits是输入字符串整个递归过程中不变传它是为了在终止条件里取digits.length()也是为了在递归体里取digits.charAt(index)。index是当前处理到第几位这是递归层数的计数器。path是当前已选的前缀比如已经选了a走到第二位时path就是“a”它是递归过程中唯一不断变化的东西。result是收集结果的列表所有叶子节点都往里面塞。这里有一个设计细节值得展开path为什么用StringBuilder不用String。因为回溯的核心操作是“前进一格再后退一格”StringBuilder可以append再加字符递归返回后deleteCharAt删掉最后一个字符原地完成撤销。String是不可变对象每次拼接都会产生新字符串你没法原地撤销只能靠传参拼接后的新串。这两种写法都能AC但用StringBuilder更能体现你理解“恢复现场”这件事。2.3 把“23”的递归树画一遍比背十遍模板都有用我不建议直接背代码建议先在纸上画递归树。以“23”为例完整过程是这样的第0层处理数字2可选字母a、b、c。选中a进入第1层。第1层处理数字3可选字母d、e、f。选dindex等于2到达终止条件收集“ad”返回。撤销dpath回到“a”。选eindex等于2收集“ae”返回。撤销epath回到“a”。选f收集“af”返回。撤销apath变成空。选中b进入第1层重复上面三步得到“bd”“be”“bf”。撤销b选中c得到“cd”“ce”“cf”。这棵树一共有3×39个叶子每个叶子对应一个结果。观察一下就能发现规律递归每深入一层path就多一个字母每返回一层path就少一个字母。撤销动作发生的位置是在当前数字的所有字母都遍历完之后把上一次选的那个字母清掉。只要这个“加一步、退一步”的节奏不乱结果就一定是对的。3. 代码落地Java回溯版、Python回溯版与BFS版三份实现3.1 Java版StringBuilder配合“加一步、退一步”直接给完整代码这是我最推荐的Java写法import java.util.ArrayList; import java.util.List; class Solution { private static final String[] PHONE { , , 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 PHONE[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); } } }核心逻辑就三块。第一块是终止条件index digits.length()说明每一位数字都已经处理完了path里存的就是完整组合加入result后直接return。这里没有显式清空path因为return之后调用它的上一层for循环会执行deleteCharAt把当前层的选择撤销掉。第二块是取选择列表PHONE[digits.charAt(index) - 0]拿到当前数字对应的所有字母。第三块是遍历选择列表先append选一个字母再递归进入下一层递归回来后马上deleteCharAt。append相当于走进这棵树的下一层deleteCharAt相当于从下一层退回上一层。这两步必须成对出现少了任何一步路径就会污染。3.2 Python版闭包写法最顺手BFS推导式也很短Python版的回溯我用闭包写法好处是不用把path和res传进传出内层函数直接访问外层变量代码更短from typing import List def letter_combinations(digits: str) - List[str]: if not digits: return [] phone [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz] res [] path [] def backtrack(index: int) - None: if index len(digits): res.append(.join(path)) return letters phone[int(digits[index])] for ch in letters: path.append(ch) backtrack(index 1) path.pop() backtrack(0) return res注意Python版里path是listappend和pop正好对应Java版的append和deleteCharAt。收集结果时用.join(path)把字符列表拼成字符串。这里的index参数也可以不传直接用len(path)判断当前处理到第几位因为path的长度天然等于已处理数字的个数。我习惯显式传index理由是逻辑一眼能看懂不容易晕。再给一个BFS版作为补充思路def letter_combinations_bfs(digits: str) - List[str]: if not digits: return [] phone [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz] res [] for d in digits: letters phone[int(d)] res [prefix ch for prefix in res for ch in letters] return resBFS版的思路很妙起始状态是空字符串前缀读一位数字就把所有前缀乘以该数字的字母数。比如一开始是[]读入2之后变成[a, b, c]再读入3之后每个前缀又扩展出3个变成9个。这本质上是把乘法原理用代码表达出来了。3.3 三份代码放在一起怎么选不纠结我列一个对比表帮你快速决策实现方式核心思想代码量是否方便扩展剪枝适合场景Java回溯递归撤销稍长很方便面试手写、系统学习Python回溯闭包递归较短很方便刷题训练、理解原理Python BFS逐层累乘最短一般快速解题、炫技实际刷题时我建议你主练一种回溯写法Java或者Python都行但必须能一口气写对。BFS记一下就行它展示的是另一种思维遇到“按层扩展”的场景会有用。面试中如果说“这道题还有一种BFS解法”一般能加分但如果不熟就别硬讲回溯讲透已经足够。4. 边界条件和经典翻车现场空串、路径污染、字符串拼接4.1 空输入返回[]还是[]很多人在这里丢分边界条件第一个坑就是空输入。题目明确说了digits为空时返回空列表[]而不是包含空字符串的列表[]。两者含义完全不同空列表表示“没有任何组合”包含空串表示“有一个长度为0的组合”。电话键盘上没有数字当然不应该产生任何字母串。如果你把res初始化为[]再去做BFS空输入时就会直接返回[]这是错的。回溯写法通常不会犯这个错因为如果入口处不挡backtrack根本不会被调用。但很多人把空串判断写成了if (digits.length() 0) return result;忘了处理digits本身为null的情况在一些平台上的隐藏用例里就会空指针。稳妥写法是入口统一判断if (digits null || digits.length() 0) { return result; }这个习惯在任何字符串处理的题目里都通用不只是这一题。养成条件反射之后面试时能省掉不少麻烦。4.2 忘记删除字符导致的路径污染长什么样回溯题翻车率最高的地方就是忘了撤销选择。以“23”为例如果backtrack末尾不写path.pop()或者Java里不写deleteCharAt会发生什么第一次走a分支path变成“a”递归进入第二层选dpath变成“ad”收集“ad”返回。返回之后path仍然是“ad”下一个循环继续append epath变成“ade”这时候收集的是“ade”不是“ae”。再往后就是“adef”全乱了。你最后得到的结果根本不是合法组合而是一堆不断变长的错误前缀。这种错误非常隐蔽因为小规模输入下前几个结果看着还有模有样你很容易以为只是顺序问题。排查方法也很简单在递归入口打印一行日志输出当前的index和path跑一遍就能看到path在回溯时没有被削减。index0 patha index1 pathad index2 pathad - 收集ad index1 pathade // 这里已经错了说明上一层的撤销没执行看到path长度不减基本就是撤销语句漏了。解决方法是把“append之后递归递归返回后立即撤销”当成一个不可分割的原子操作不要穿插任何提前return的逻辑。4.3 String拼接能过吗能但我们别这么写还有一种写法也能AC就是path不用StringBuilder直接用String拼接递归时传入path letters.charAt(i)这样每一层都是新的字符串天然不存在路径污染问题。代码确实更短void backtrack(String digits, int index, String path, ListString result) { if (index digits.length()) { result.add(path); return; } String letters PHONE[digits.charAt(index) - 0]; for (int i 0; i letters.length(); i) { backtrack(digits, index 1, path letters.charAt(i), result); } }但我不建议你这么写原因不是性能而是它掩盖了回溯的本质。回溯的精髓是“同一份路径状态反复使用先加后撤”String不可变你等于每层都复制了一份完整字符串。当digits长度变成十几位、组合数爆炸的时候这种写法会产生大量临时字符串GC压力肉眼可见地上升。更关键的是面试官问你“为什么不需要撤销”你得解释半天String的不可变性反而把自己绕进去了。用StringBuilder并正确撤销是更标准、更符合回溯思维的做法。5. 复杂度分析不能只背结论组合数、递归栈和结果集5.1 组合总数是各数字字母数的乘积不是指数固定3很多人张口就说时间复杂度是O(3^n)因为每个数字平均3个字母。这个说法其实粗糙了7和9对应的是4个字母。严谨的推导是这样的设digits长度为N第i位数字对应的字母数量为len[i]那么叶子节点总数就是各len[i]的乘积而不是简单的3的N次方。最坏情况是所有数字都是7或9每个数字贡献4个字母叶子数是4^N。所以上界写成O(4^N)更安全。如果输入是“234”三位数字都是3个字母总组合数就是3×3×327如果输入是“79”结果是4×416。真实组合数要看输入的具体构成分析时用上界即可。完整的时间复杂度还要算上每个叶子节点生成字符串的开销。递归树上经过的节点总数大致是1 4 4^2 ... 4^N这是一个等比数列渐进复杂度仍然是O(4^N)量级。而每次到达叶子时path.toString()或.join(path)需要把长度N的路径复制出来这个操作是O(N)的。所以整体时间复杂度是O(N × 4^N)。能在面试里主动说出“这里还有一个N的因子”通常会让面试官眼前一亮。5.2 空间复杂度要算两部分结果集经常被漏掉空间复杂度这里有个容易混淆的点。如果不算输出结果所占的空间辅助空间主要是递归调用栈的深度每层存了index和一些局部变量所以是O(N)。这是很多人背的答案。但如果我们讨论整个算法占用的总空间结果集本身也必须算进去。假设有K个组合每个组合长度N结果集空间就是O(N × K)最坏情况下K4^N所以总空间是O(N × 4^N)。很多新手只回答“O(N)”被追问不是答错而是没分清楚“辅助空间”和“总空间”两个口径。我建议的表述是递归栈深度O(N)不算输出的话辅助空间O(N)如果算上存储所有结果的空间那还要再加一个O(N × 4^N)。这样既准确又严谨。5.3 为什么说它是回溯入门最友好的一题说回这道题本身的价值。它没有去重问题没有剪枝条件没有额外的约束校验每个数字的选择列表都是完全独立的互不影响。你只需要关注一件事如何在递归进入和返回时维护好当前路径。但别看它简单回溯的三个核心要素它全占了路径path、选择列表当前数字对应的字母、终止条件index到达digits末尾。这三个要素在任何回溯题里都是不变的骨架区别只在于选择列表怎么更新、终止条件怎么判断、需不需要剪枝。把这道题当成练兵场把“加一步、退一步”练成肌肉记忆后面刷全排列和子集时会非常顺。6. 一道入口题如何打通一类题回溯模板与扩展路线6.1 回溯的万能模板五步对应到这题上我总结过一个回溯五步法每次写题都按这个顺序思考确定递归函数参数想清楚哪些变量需要跨层传递哪些变量只在本层使用。确定终止条件想想什么时候收集结果并返回。确定单层搜索过程也就是for循环怎么遍历选择列表。做选择把当前选中的值加入路径。撤销选择递归返回后把路径恢复到进这层之前的样子。套到这道题上第一步参数是digits、index、path、result第二步终止条件是index等于digits长度第三步for循环遍历当前数字对应的字母串第四步append第五步deleteCharAt/pop。每一步都有明确的代码落点不是玄学。这个模板对全排列同样成立参数里加一个visited数组记录哪些元素已经用过终止条件是路径长度等于数组长度选择列表不再是固定字符串而是数组中未被访问过的元素撤销时除了删路径元素还要把visited标记恢复。你会惊讶地发现只要把模板套进去代码结构几乎不变。6.2 本题没有剪枝但可以体会剪枝入口在哪很多回溯题都会涉及剪枝比如组合总和中如果当前路径和已经超过目标值就不再继续递归。这道题没有任何约束条件所有组合都必须收集所以没有真正意义上的剪枝。但有一个天然“剪枝”的地方值得体会如果输入里出现0或1现实中电话键盘确实有这两个键但它们没有字母对应的letters是空字符串for循环根本不会执行递归函数直接返回。效果就是这个分支自动被砍掉了。对这道题的官方约束来说根本不会触发但你能在刷题时意识到“不进入循环就是剪枝”这件事说明你已经理解了剪枝的本质在进入更深层递归之前提前终止那些不需要探索的路径。6.3 接下来按什么顺序刷全排列、子集、组合总和这道题练熟之后我建议按这个顺序继续刷全排列、子集、组合总和。它们和电话号码这题的差别刚好覆盖回溯的各种经典变体。全排列是“选择列表动态缩小”的典型每层选择一个数字后下一层不能再选它所以需要visited数组维护剩余选择。子集是“结果收集时机不同”的典型需要在每个节点都收集当前路径而不是只在叶子收集。组合总和是“剪枝的典型”可以重复选择同一个元素但要求组合的和等于目标值超了就必须剪掉。这三道题吃透回溯基本就通了。回头再看这道电话号码它最可贵的地方是干净。没有重复元素、没有和值限制、没有顺序要求你可以在完全不受干扰的情况下把“递归进入”和“状态回退”这两个动作练到条件反射。我在实际练习中的体会是第一遍写错不要紧先打印递归日志看路径变化确认撤销动作和执行顺序没问题再对照模板调整。很多人刷题喜欢追求一次AC但碰到回溯题我更建议把错误路径亲手跑一遍看看path是怎么一步步累积又一步步收缩的。这道题是你建立这种感觉最好的起点把它啃透后面刷任何回溯题都会觉得顺畅许多。最后分享一个小技巧在for循环里先把letters取出来放在局部变量里命名清楚调试时打日志也方便面试时还能顺带展示你的代码整洁度。