题目描述
给一串数字（2-9），按九宫格键盘映射，返回所有可能的字母组合（顺序不限）。
思路解析
两位写两层 for、五位写五层……可 digits 的长度是变量，层数不固定，嵌套循环根本写不出来，这是暴力解卡死的地方。
转折：用递归替掉「不定层循环」。先建好键盘映射 {2:abc, 3:def, ...}；递归到第 i 位时，枚举 digits[i] 对应的几个字母，每选一个就 i+1 去定下一位；i 走到末尾说明每位都定好了，把 path 拼成串收进结果，然后撤销刚才那个字母，回上层换下一个。选→递归→撤销，三步循环。
第 1 位 "2" · 选 a：从第 1 位开始，digits[0]="2" 的候选是 a/b/c。先选 a，path=["a"]，还没到末尾，i+1 进入第 2 位。
第 2 位 "3" · 选 d → 收 "ad"：切到第 2 位：候选换成 digits[1]="3" 的 d/e/f（格子里的字母随之换成 d/e/f）。选 d，path=["a","d"]，i 已到末尾——两位都定完，拼成 "ad" 收进结果。
撤销 d（回溯）· 换 e → 收 "ae"：负例/回溯动作：把刚选的 d 弹出，path 退回 ["a"]，d 重新变回「可选」。不撤销的话第 2 位会越积越长、串到下一个字母里。撤销后在第 2 位改选 e，收下 "ae"。
第 2 位 · 再换 f → 收 "af"：同样撤销 e、改选 f，收下 "af"。第 2 位的 d/e/f 都和 a 配过了，a 打头的三种全齐。接着把第 2 位整个撤销、退回第 1 位换头。
换第 1 位 · 选 b：回到第 1 位，候选又变回 a/b/c。a 撤销后改选 b，path=["b"]，再 i+1 去定第 2 位。流程和 a 打头时一模一样。
第 2 位 "3" · 选 d → 收 "bd"：第 2 位又切到 d/e/f。选 d，path=["b","d"]，到末尾，收下 "bd"。接着同样撤销换 e、换 f，能收 "be"、"bf"。
b 打头收齐 · 准备换 c：b 配完 d/e/f，收下 "be"、"bf"。b 打头的三种也全了。再撤销退回第 1 位，最后把头换成 c。
换头 c · 收齐全部 9 个：c 打头同样配 d/e/f，收下 "cd"、"ce"、"cf"。最终 9 种组合不重不漏全部收齐，正好是 3×3。
「多个位置、每个位置有几种选法、求全部搭配（笛卡尔积）」的通用解法：一层递归管一位，到底就收。位数不定时，它替你写出「层数随输入变化」的循环。
参考代码（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, path = [], []
6 def bt(i):
7 if i == len(digits): # 每位都定完了
8 res.append(class="cl-str">"".join(path)); return # 拼成串收下
9 for ch in M[digits[i]]: # 枚举本位的字母
10 path.append(ch) # 选
11 bt(i + 1) # 去定下一位
12 path.pop() # 撤销（回溯）
13 bt(0)
14 return res复杂度分析
- 时间复杂度：O(4^n · n) —— n 位、每位最多 4 字母，拼每个串再花 O(n)
- 空间复杂度：O(n) —— 递归深度 = 位数 n，path 也最多 n 长
套路模板
骨架：用 i 标记当前是第几位，i 到底就收快照，否则枚举本位候选、append 选、递归 i+1、pop 撤销。位数不定的「笛卡尔积」全套它。
1def bt(i, path):
2 if i == 总位数:
3 res.append(path 的快照); return
4 for 选项 in 第 i 位的候选:
5 path.append(选项)
6 bt(i + 1, path) # 关键：i+1 下探
7 path.pop() # 撤销易错点
- 错误写法：收集时机判 i == len(digits)-1 → 正确写法：i == len(digits) 才收（定完最后一位后 i 会 +1 到 len(digits)，那一刻每位才都定好，提前一格收会漏掉最后一位的字母）
- 错误写法：digits 为空时返回 [""] → 正确写法：空输入直接返回 []（空串没有任何组合，返回 [""] 会凭空多出一个假结果）
- 错误写法：把 7、9 当成 3 个字母 → 正确写法：7→pqrs、9→wxyz 各是 4 个（映射表要照键盘抄准，7 和 9 各有 4 个字母，写错就漏掉组合）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。