从九键字母组合入手，彻底搞懂DFS回溯与递归遍历

九键字母组合应该是深度优先遍历DFS最友好的入门题之一也是很多人在算法习题集里遇到的第一个回溯类题目。我第一次拿它练手时第一反应是“数字不就固定几位嘛几个for循环叠起来就完事”可一旦输入变成“2345”“23456789”这种不定长字符串循环层数根本没法写。真正该做的是把每个数字对应的字母看作一层的可选分支一层层往下走、走到头就记录结果、再回退到岔路口走别的分支——这正是DFS回溯的核心节奏。这篇文章围绕九键字母组合这道题把DFS的树形模型、递归实现、复杂度、迭代写法以及容易踩的坑完整过一遍。不管你是刚接触算法的学生还是准备面试的开发者照着这份思路敲一遍代码组合类问题基本就算是入了门。1. 先看清九键键盘的映射关系再谈DFS1.1 题目到底在求什么题目本身一句话就能讲清老式功能机键盘上2到9这几个数字键分别对应一组字母2对应abc3对应def4对应ghi5对应jkl6对应mno7对应pqrs8对应tuv9对应wxyz。给定一串数字比如“23”要输出所有可能的字母组合也就是把第1位数字对应的3个字母和第2位数字对应的3个字母两两配对得到 [ad, ae, af, bd, be, bf, cd, ce, cf]。注意这里虽然叫“字母组合”和数学里的组合 C(n,k) 不是一回事。数学组合不要求位置顺序这道题则强调位置结果字符串的第1个字符必须来自输入串第1位数字对应的字母组第2个字符必须来自第2位数字对应的字母组。换句话说每一位的选择集合是固定的整个问题本质上是在求这些集合的笛卡尔积。理解了这一点就不会在实现时把字母顺序搞混。输入“23”输出 3×39 个结果输入“234”输出 3×3×327 个。数字位数 n 决定了输出字符串的长度也决定了搜索树的深度。这一点是后面复杂度分析的基础先把模型建起来代码才不容易写偏。1.2 映射表怎么设计数组还是字典映射关系是这道题的地基。最常见的是用数组按下标存下标2对应abc3对应def以此类推。数组前两个位置0和1留空就行。这样做的好处是数字字符转成下标特别自然int(2) 就是 2直接 mapping[int(digits[index])] 取出候选字母代码很干净。方式写法示意适用场景数组mapping [, , abc, def, ...]输入保证是0-9数字字符索引直观字典mapping {2: abc, 3: def, ...}增加特殊键、可读性要求更高如果对数字字符和 int 之间的距离感到别扭也可以用 ord(digits[index]) - ord(0)一样能拿到数字。这个细节虽然小但面试时能写出整数转换而不是 char 拼接会显得更扎实。我个人的推荐是数组方案。这道题的输入范围固定数组索引访问是 O(1)而且不用频繁做字符串查找如果未来要在0和1上挂特殊含义改成字典也很容易把默认行为抽成函数就行。1.3 边界情况先问清楚刷题版本的输入一般保证只含2到9但真实的使用场景未必。拿到题目先把边界确定下来digits 为空时应该返回什么标准答案多数是返回空列表 []因为没有任何数字可以产生字母组合。有少数早期版本会返回 []面试时主动确认一下就是加分项。如果输入可能含0或1而题目又没有说明我的习惯是先向出题人确认是跳过、直接报错还是有特殊映射后面专门有一节说这个话题这里只需要记住好的解法一定会把边界放进代码里而不是默认输入永远合法。2. 为什么这类组合枚举天然适合DFS2.1 把选择过程画成树假设输入是“23”。第1位数字2有三个候选字母 a、b、c形成三根树枝第2位数字3有三个候选 d、e、f每一根树枝上再分三根。最终这棵多叉树有9片叶子每一片叶子对应一个完整结果。DFS 的思路就是沿着树的深度方向走从根出发先走到 a再从 a 往下走到 ad记录 ad回到 a 节点再往下走到 ae……直到遍历完所有分支。递归天然适合这种“进入子节点-返回父节点”的结构因为每次递归调用就相当于下探一层函数返回就自动回到上一层。这也解释了为什么递归实现里终止条件通常是 index len(digits)当处理完最后一位数字时path 中的字母个数已经等于输入数字个数此时已经走到叶子节点可以记录结果了。2.2 递归三步选择、深入、回退顺着树的视角写伪代码核心只有三件事。第一在当前层第 index 位数字依次取每个候选字母第二把候选字母加入当前路径并继续处理下一位第三从路径中移除刚才加入的字母回到这层循环的下一个候选。def dfs(index, path): if index len(digits): result.append(.join(path)) return for ch in mapping[int(digits[index])]: path.append(ch) # 选择 dfs(index 1, path) # 深入 path.pop() # 回退别看代码短这三个动作的顺序一个都不能乱。选择放在递归前是为了让子问题看到“我已经选了 ch”的状态回退放在递归后是为了恢复现场让同一层的下一个候选拥有完全相同的起点。这里也顺带提一个工程层面的点递归是有调用栈承载的深度太大时可能爆栈。九键题目的输入位数一般不会超过几十位问题不大但如果你在别的 DFS 题目里要处理上万层的递归就得考虑改用显式栈模拟避免踩到递归上限。2.3 回溯到底回退了什么很多初学者把 path.pop() 看成可有可无的收尾其实它才是 DFS 回溯的灵魂。想象你在走一个树形迷宫走到某条树枝的尽头记下路径后如果不退回上一个岔路口就没法走第二条树枝path.pop() 干的就是“退回岔路口”这件事。如果不做 pop会发生什么以一个两层递归为例处理完 a → d 之后path 是 [a, d]若不 pop 就去尝试 a → epath 会变成 [a, d, e]长度变成了3和输入位数对不上结果自然全错。所以记住递归进去时做了什么操作返回前必须原样撤销这是一条通用原则后面的排列、组合、矩阵搜索全都适用。顺带说一句有人喜欢用字符串拼接 s ch 代替 list 加 pop。这样写更短每层递归都创建新字符串不会有污染问题。但理解“状态恢复”这个思想时list pop 的方式更直观后续做更复杂的回溯题也更不容易出错。两种我都写过平时刷题用 list面试时也会顺带解释一句为什么要 pop。3. 完整实现与逐行拆解标准递归版3.1 Python 标准写法from typing import List class Solution: def letterCombinations(self, digits: str) - List[str]: if not digits: return [] mapping [, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz] result [] def dfs(index: int, path: list) - None: if index len(digits): result.append(.join(path)) return letters mapping[int(digits[index])] for ch in letters: path.append(ch) dfs(index 1, path) path.pop() dfs(0, []) return result这段代码有几个细节值得说。第一个空输入在前面直接 return []避免后续递归把空串当作唯一结果第二个mapping 下标从0开始所以下标0和1特意留了空字符串避免把 digits 里的 2 转成 int 后越界第三个dfs 内层函数捕获了 digits、mapping、result 这三个变量Python 闭包会保持引用理解这一点之后变量作用域就不会再成为障碍。建议第一次接触这段代码的人拿“23”当用例在纸上把递归过程完整走一遍dfs(0) 进入 a 后调用 dfs(1)dfs(1) 进入 d 后调用 dfs(2)此时 index 等于 len记录 ad然后一层层返回。这个过程走通递归的肌肉记忆基本就建立了。3.2 Java 递归版StringBuilder 的回退class Solution { private final String[] mapping { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; private ListString result new ArrayList(); public ListString letterCombinations(String digits) { if (digits null || digits.length() 0) { return result; } backtrack(digits, 0, new StringBuilder()); return result; } private void backtrack(String digits, int index, StringBuilder path) { 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); path.deleteCharAt(path.length() - 1); } } }Java 版的核心配对操作是 append 和 deleteCharAt。StringBuilder 是可变对象递归中不断追加和删除正是为了复用同一个缓冲区如果每次递归都 new StringBuilder()代码虽然简单但内存开销会对应增大。注意 char 转索引用的是 digits.charAt(index) - 0这是字符串转数字的常见写法比先转 String 再 parseInt 要快。实现类里如果反复多次调用 letterCombinations最好在方法开头清空 result避免上一次调用残留数据污染本轮结果。这是一个隐蔽但很实在的工程细节。3.3 为什么这道题不需要写剪枝常见的 DFS 题目里经常能听到“剪枝”这个词比如走迷宫时发现前方是墙就提前回头。于是有人会问这题要不要剪枝我的答案是不需要因为每一个从根到叶子的路径都是合法的没有任何“走一半发现没救”的分支。二维网格搜索中会出现无效格子、N皇后中会出现同行同列冲突这些都需要提前判断来减少无用递归而九键字母组合每一位的候选字母完全独立当前选择了哪个字母对后续选择没有任何约束。正因如此这道题的时间复杂度就是输出结果数本身没有任何优化可以让它低于枚举量级。先把“本题不需要剪枝”想明白后面做带约束的回溯题才知道剪枝该加在哪里。4. 复杂度分析指数级到底有多大4.1 时间开销跟着输出规模走设输入数字个数为 n。每一位数字对应的字母个数可能是3个或4个最坏情况下每位都是4个候选于是组合总数最多是 4^n。每生成一个结果需要从 path 拼接出长度为 n 的字符串这一步又是 O(n)。所以最坏时间复杂度是 O(4^n * n)这也是这一类枚举题的典型复杂度。如果输入全是2到6这类三字母数字组合总数就是 3^n混合输入就在 3^n 到 4^n 之间。所以面试时直接说“最坏 O(4^n * n)”是没问题的前提是 n 指数字串长度。日常讨论这类题目时把 n 和单个数字的候选字母数分清楚复杂度表达才不会含糊。4.2 空间开销主要让结果集背锅递归栈深度最多 n所以递归本身只占用 O(n) 的临时空间。真正的大头是最终返回的结果列表4^n 个字符串每个长度 n结果集占 O(4^n * n)。如果不把结果存储算进辅助空间只说额外空间复杂度就是 O(n)。这一点在面试里容易引起分歧我的建议是把“结果集”和“递归辅助空间”分开讲前者是题目要求的输出后者才是我们实现的额外开销。这样表述既严谨也不会把自己绕晕。空间复杂度的口径问题在很多题目里都存在提前养成区分习惯会省掉很多口舌。4.3 直观感受一下规模拿几个输入感受一下数量级。两位数字“23”有9个组合三位“234”有27个四位“2345”有81个。哪怕输入直接给满“23456789”也就是 3×3×3×3×3×4×3×4 11664 个组合对现代计算机来说眨眼就能算完。但一旦数字位数变长比如10位且全部是7或9最坏就是 4^10 ≈ 1048576超过一百万条结果光是存结果字符就要约一千万字节。到这个规模内存和耗时都会明显上升。所以这类题适合做入门训练真要处理超长输入就得考虑动态规划或计数方法纯枚举会撞墙。理解 4^n 的增长速度是设计解决方案前最重要的一步。5. 不递归也能做队列模拟 BFS 的迭代版5.1 一层层扩展的思路DFS 是顺着一条路走到黑再回头迭代版则反过来先处理第1个数字生成所有一位前缀再处理第2个数字把每个一位前缀扩展成两位前缀依此类推。这个“每一轮扩展一层”的过程本质上就是广度优先遍历可以用队列来模拟。以“23”为例初始队列里只有一个空串。读入数字2后弹出空串分别接上 a、b、c队列变成 [a, b, c]读入数字3后先弹出 a接上 d、e、f 得到 ad、ae、af再弹出 b继续接……直到队列里的所有前缀都变成两位。最终队列里就是全部9个结果。5.2 DFS 和 BFS 在本题上的对比维度DFS 递归版BFS 迭代版状态保存依赖系统递归栈显式维护队列结果生成时机递归到叶子时才拼接每轮扩展时生成完整前缀代码直观度短但需要理解递归不需要递归循环直白内存递归栈 O(n)队列最多存当前层前缀整体同样 O(4^n n)两种写法拿到的结果集合完全相同只是输出顺序可能有差异。题目一般只要求返回全部组合不规定顺序所以选哪种都可以如果某个场景要求字典序那就要注意控制遍历顺序比如每次按候选字母的原始顺序扩展即可自然保持字典序。5.3 迭代版代码from collections import deque def letterCombinations(digits: str): if not digits: return [] mapping {2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz} queue deque([]) for digit in digits: letters mapping[digit] for _ in range(len(queue)): prefix queue.popleft() for ch in letters: queue.append(prefix ch) return list(queue)这里有个容易写错的细节内层循环的次数必须在一开始就取 len(queue)因为循环过程中队列会不断追加新元素。如果写成 while queue 然后每次取大小处理逻辑会乱。另一种更懒的写法是每轮直接用新列表构造res [p ch for p in res for ch in letters]一行搞定代码最短但面试时我会更推荐显式队列版本因为它把“逐层扩展”的状态讲得更清楚也方便后续迁移到其他分层遍历场景。6. 实战里容易踩的坑以及下一个进阶方向6.1 四个高频 bug错误现象修复没把 path 转成字符串就加入结果返回一堆空列表或地址引用result.append(.join(path))忘记 path.pop()路径跨分支累积结果长度错乱每次递归返回前撤销选择用字符直接当数组下标抛 TypeErrorint(digits[index]) 或 char - 0空输入返回 []与题目期望 [] 不符入口处单独判断空输入第一个坑我见过太多次path 是一个可变 list如果直接 result.append(path)最终保存的是同一个对象的引用递归结束 path 被清空结果集里全是空列表。这不是算法思路错而是语言层面的引用问题但考试和面试都不会给你辩解机会。第二个坑的根因在于没理解回溯的对称性append 了多少个字符递归返回后就要 delete 或 pop 多少个。调试时可以在 dfs 开头打印 index 和 path看到路径长度不对百分之百是这里的问题。这种打印调试法对排查所有递归问题都有效比干瞪眼硬想快得多。6.2 如果数字 0 和 1 参与进来标准刷题环境下输入只会是2到9所以 mapping 里下标0、1空着也没人踩雷。但真实电话键盘上0和1确实存在只是没有对应字母。遇到这种扩展我建议先和出题人确认规则。常见的几种处理策略是直接跳过0和1这样输出字符串的长度可能小于输入长度遇到就抛异常快速失败或者给0和1挂特殊字符映射。没有标准答案关键是把边界处理写清楚并且测试用例覆盖到。面试时你能主动抛出这个点反而比闷头写一个只过样例的版本更有记忆点。6.3 一个模板吃透 DFS 回溯我把这道题写下来后最大的收获是提炼出一个回溯模板后面做全排列、组合、二维网格搜索时都能复用def backtrack(路径, 选择列表): if 满足结束条件: 记录路径 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择九键字母组合里的“选择列表”是当前数字对应的字母集合全排列里的“选择列表”是还没有被用过的元素需要加 visited 数组组合问题要在 for 循环里加 start 下标防止重复二维网格搜索则要在做选择前检查边界和是否已访问。骨架大概率不变变的只是“如何生成选择列表”和“如何判断结束条件”。从我自己的刷题体验来说DFS 回溯最难的不是写代码而是真正理解“撤销”这一步为什么会带来正确结果。我后来养成了一个笨办法遇到递归题先拿一个只有两层的小输入在纸上手动走一遍递归再把打印函数加进去观察每一次入栈、出栈时 path 的变化。这套流程看起来慢但对建立递归直觉特别管用。九键字母组合作为 DFS 的入门题意义也在于此它没有任何剪枝和额外约束能让新手毫无干扰地体会“选择、深入、回退”的完整节奏。把这道题的肌肉记忆练成之后再去碰排列组合、岛屿数量、单词搜索你会发现自己已经知道下一步该往哪儿走了。