电话号码的字母组合

电话号码字母组合在问什么

给一个只含 2 到 9 的数字串，每个数字像老式电话键盘那样对应几个字母（2 对 abc、3 对 def，7 和 9 各对 4 个），要求列出这串数字能表示的所有字母组合。以 "23" 为例，第一个字母从 abc 里挑、第二个从 def 里挑，共 3×3 等于 9 种。本质上这是在求「每位各选一个字母」的所有搭配方式，也就是若干组候选字母的笛卡尔积，而且要全部列出来，不是数个数。

为什么不用嵌套循环而用回溯

两位数字写两层循环、三位写三层，思路没错，但输入的位数是变量，循环层数没法写死，代码无法对任意长度通用。这是所有「层数不定的枚举」共同的困境。

出路是把「一层循环」换成「一层递归」：定义 backtrack(i) 表示正在为第 i 位数字挑字母，函数体里一个 for 循环枚举这一位的候选，选中一个就递归到 backtrack(i + 1) 处理下一位。递归深度自动等于数字位数，等于用一个函数写出了任意层的嵌套循环——这正是回溯算法处理这类枚举题的通用骨架。

path 和递归参数 i 的含义要先钉死

参数 i 表示前 i 位数字都已选好字母、现在轮到第 i 位；path 里存的正是这前 i 个字母。两者构成一条不变量：任何时刻 path 的长度恰好等于 i。于是终止条件水到渠成——当 i 等于 digits 的长度，说明每一位都选过了，把 path 连接成字符串收进结果即可。

每层的候选集合由 digits 的第 i 个字符查表得到，比如查到 "def" 就依次尝试 d、e、f。同一层的三个选择彼此平行，各自往下展开一棵子树，所有叶子加起来正好是全部组合，不重也不漏。

为什么递归回来必须 pop 掉刚选的字母

path 是整棵递归树共享的同一个缓冲区，不是每层复制一份。递归从 backtrack(i + 1) 返回时，意味着「以刚才那个字母打头的所有后续组合」已经收集完毕，必须把它从 path 末尾弹出，恢复到选它之前的状态，才能在同一层干净地换下一个字母。不弹的话，上一个选择会残留在 path 里污染后面的分支，拼出的字符串位数和内容全错。先 append、递归、再 pop，这三步的对称性就是回溯正确性的全部保证。

复杂度与两个必踩的边界

时间 O(4ⁿ·n)：每位最多 4 个候选字母（数字 7 和 9），组合总数最多 4ⁿ 个，每个组合拼成字符串还要 O(n)。空间 O(n)：递归深度与 path 长度都等于位数，结果本身不计。

两个边界最容易翻车：一是 digits 为空必须直接返回空数组，而不是含一个空串的数组——没有输入就没有任何组合；二是映射表要从 2 开始建，0 和 1 不对应字母，且 7 对 pqrs、9 对 wxyz 各是 4 个字母，错位一格全盘皆输。