题目描述
给一串数字（2-9），按九宫格键盘映射，返回所有可能的字母组合。
digits = "23"
映射 = 2→abc, 3→def
输出 = ad ae af bd be bf cd ce cf
思路解析
两位写两层 for，五位写五层……位数是变量时，又卡在「层数不固定」上了。
把「定每一位」交给递归：当前位每选一个字母，就往下去定下一位，所有位都定完就收一条。
先建好键盘映射 {2:abc, 3:def, ...}。递归到第 i 位时，就去枚举 digits[i] 对应的那几个字母。
第 1 位 "2" → 选 a：第一位是 2，候选 a/b/c。先选 a，路径 "a"，接着去定第二位。
第 2 位 "3" → 选 d：第二位是 3，候选 d/e/f。选 d，路径 "ad"，两位都定完了，收进结果。
回溯：a 配 e、配 f：退回第二位，把 e、f 也试一遍，收下 "ae"、"af"。a 打头的就全了。
换第一位：b、c 打头：再回到第一位换成 b、c……最终 9 种组合全部收齐。
「多个位置、每个位置有几种选法、求全部搭配」的通用解法：一层递归管一位，到底就收。
参考代码（Python）
Python
1def letterCombinations(digits):
2 if not digits: return []
3 M = {class="cl-str">"2":class="cl-str">"abc",class="cl-str">"3":class="cl-str">"def",class="cl-str">"4":class="cl-str">"ghi",class="cl-str">"5":class="cl-str">"jkl",
4 class="cl-str">"6":class="cl-str">"mno",class="cl-str">"7":class="cl-str">"pqrs",class="cl-str">"8":class="cl-str">"tuv",class="cl-str">"9":class="cl-str">"wxyz"}
5 res = []
6 def bt(i, path):
7 if i == len(digits): # 每位都定完了
8 res.append(class="cl-str">"".join(path)); return
9 for ch in M[digits[i]]: # 枚举这一位的字母
10 bt(i + 1, path + [ch]) # 去定下一位
11 bt(0, [])
12 return res复杂度分析
- 时间复杂度：O(4ⁿ · n) —— n 位、每位最多 4 字母
- 空间复杂度：O(n) —— 递归深度 = 位数
套路模板
骨架：用 i 标记当前是第几位，到底就收，否则枚举本位候选、递归 i+1。位数不定的「笛卡尔积」全用它。
Python
1def bt(i, path):
2 if i == 总位数:
3 res.append(path 的快照); return
4 for 选项 in 第 i 位的候选:
5 bt(i + 1, path + [选项])易错点
- ❌ digits 为空时返回 [""] → ✅ 空输入直接返回 []（空串没有任何组合，返回 [""] 会多一个假结果）
- ❌ 把 7、9 当成 3 个字母 → ✅ 7→pqrs、9→wxyz 是 4 个（映射表照键盘抄准，7 和 9 各有 4 个字母，写错就漏组合）
- ❌ 终止条件用 i == len(digits)-1 → ✅ i == len(digits)（定完最后一位后 i 会到 len(digits)，那一刻才该收）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。