电话号码的字母组合
Letter Combinations of a Phone Number
给定手机九宫格上的数字串，返回它能表示的所有字母组合。
在力扣中练习题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "2" 输出：["a","b","c"]
提示：
1 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解题思路
回溯 · 逐位选字母
每个数字选一个字母，选满 digits 长度就收集
组合的长度固定等于 digits 的长度，每一位从对应数字的字母集合里选一个。这正适合回溯：递归层数就是数字位置。
进入第 pos 位时，遍历它对应的所有字母；选一个、递归下一位、再撤销。到达 pos == digits.size() 时，path 就是一个完整组合。
digits="24" 表示要取 2 个字母；空输入直接返回空结果。
自拟输入 "24"：2 对应 abc，4 对应 ghi，共 3×3=9 种。画面上 path 随选择增长，res 只在叶子收集。
path "bg" 已经覆盖所有数字，复制进 res。
- res.size
- 4
每个数字最多 4 个字母，时间 O(4ⁿ·n)（拼接结果占主导），递归深度 O(n)。空输入必须返回空结果，而不是包含空串的数组。
易错点
- 空输入没有单独处理：会返回 [""]，而题目要求 []。
- 把 digits 的长度当成字母总长度：递归终止条件写错。
- 忘记 path.pop_back()：不同数字的字母会串在一起。
迭代 · 逐位做笛卡尔积
从空串开始，每读一个数字就把结果集扩充一遍
空间峰值保存所有中间组合，最坏 O(4ⁿ)；回溯版只占 O(n) 路径。
把结果看成一个不断扩大的集合：初始只有空串。每读一个数字，就把当前每个字符串分别接上该数字的每个字母，生成下一轮结果。
这是标准的笛卡尔积展开，代码没有递归，顺序也与回溯一致；代价是中间结果集可能非常大。
当结果数量本来就很大时，两者都无法避免输出规模；如果只要求第 k 个组合，回溯可以提前停止，迭代版则不适合。
- 1结果集初始化为 [""]。
- 2遍历每个数字。
- 3把每个已有字符串接上该数字的每个字母。
- 4用新结果集替换旧结果集。
易错点
- 空输入仍返回 [""]：需要提前返回空数组。
- 在遍历 res 的同时修改 res：会不断读到刚生成的新串。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
digits = "24"digits="24" 表示要取 2 个字母；空输入直接返回空结果。
查看 C++ 代码
延伸阅读
- 组合类回溯的终止条件通常是“位置走完”，而不是“和达到目标”；先明确这一点再写循环。
- 如果数字包含 0 或 1，需要对空字母集做特殊处理，否则结果会变成空。