一句话说明核心方法把 digits 的每一位看作决策树的一层,每层从当前数字对应的一组字母里选一个,用回溯 DFS 走完所有层,叶子节点拼出的字符串就是一个合法组合。思路推导题意转化:输入23,本质是第 1 位从abc里选一个,第 2 位从def里选一个,两个位置各做一次选择 → 笛卡尔积。关键观察:这是一棵多叉决策树——树的层数 digits.length(),第 i 层的分支数 digits[i]对应字母的个数(3 或 4)。答案就是所有根到叶子的路径。算法选择:既然要枚举所有路径,回溯是最自然的工具。用一个StringBuilder path记录当前路径,走到最后一层就收集。和子集题的关键区别:子集是二叉决策(每个元素选/不选),每层只有 0/1 两种分支,且每个节点都是答案;本题是 k 叉决策,每层分支数由数字决定,只有走到最后一层(index length)才是一个完整组合。所以收集点从每个节点变成了仅叶子节点。回溯树示意(digits 23) ← index0,path 为空 ┌────────────┼────────────┐ a b c ← digits[0]2 → abc │ │ │ index1 index1 index1 a b c ┌─┼─┐ ┌─┼─┐ ┌─┼─┐ d e f d e f d e f ← digits[1]3 → def │ │ │ │ │ │ │ │ │ ad ae af bd be bf cd ce cf ← index2,收集(叶子) 共 3 × 3 9 个组合注意每层 for 循环遍历的不是nums全部元素,而是当前数字对应的那几个字母;层数固定为digits.length(),不深不浅。Java 完整代码class Solution { // 数字到字母的映射:下标 0/1 占位为 ,2→abc ... 9→wxyz String[] map {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; ListString res new ArrayList(); public ListString letterCombinations(String digits) { // 空串特判:否则会错误地收集一个 if (digits null || digits.length() 0) { return res; } backTrack(digits, 0, new StringBuilder()); return res; } private void backTrack(String digits, int index, StringBuilder path) { // 终止条件:已经处理完所有数字,path 就是一个完整组合 if (index digits.length()) { res.add(path.toString()); return; } char ch digits.charAt(index); String letters map[ch - 0]; // 当前层的候选字母集 for (int i 0; i letters.length(); i) { path.append(letters.charAt(i)); // 1. 选 backTrack(digits, index 1, path); // 2. 递归到下一层 path.deleteCharAt(path.length() - 1); // 3. 撤销 } } }关键代码逐行解释map[ch - 0]:字符2的 ASCII 是 50,0是 48,相减得到整数 2,正好作为数组下标取到abc。这比写switch或一长串if-else简洁得多,也是本题最常用的技巧。if (index digits.length())作为终止条件:走到这里说明每一位都选完了,path长度恰好等于digits.length(),是一个完整组合。这是叶子收集的典型写法——只在满足长度条件时收,不像子集题每个节点都收。String letters map[ch - 0]而不是在 for 里直接写map[digits.charAt(index) - 0].length():先把候选集提出来,for 循环里只做取字母,读写更清爽,也避免重复计算。path.deleteCharAt(path.length() - 1):StringBuilder 的撤销操作,删掉最后加的字符。别写成deleteCharAt(index)——index是层号,不是字符位置,这样删会出错。res.add(path.toString()):必须toString()生成一份新的 String。如果直接res.add(path)类型都不对;即便类型转成 String 再共享引用,后续递归改了 StringBuilder,已加入的结果也会跟着变。时间、空间复杂度时间复杂度:O(n · 4ⁿ)(n digits.length())决策树叶子数上界为 4ⁿ(每个数字最多对应 4 个字母),每个叶子执行一次path.toString()生成长度为 n 的字符串,故上界 O(n · 4ⁿ)。因为 n ≤ 4,实际规模极小。空间复杂度:O(n)(不计输出)递归栈深度为 n,StringBuilder path长度也为 n。输出结果本身占 O(4ⁿ · n),题目要求返回,无法避免。易错点空串没特判:如果题目允许digits ,代码会执行到index 0 length,收集一个空字符串,结果变成[]。正确结果应是[],所以入口要加if (digits.length() 0) return res;(本题约束length 1,但面试/旧版题目常考这个边界)。忘了toString():用StringBuilder累积路径时,必须res.add(path.toString())拷贝一份。直接存引用会让所有结果指向同一个对象,最后全被后续递归改掉。撤销位置写错:deleteCharAt(path.length() - 1)删的是最后一个字符;写成deleteCharAt(index)(层号)会删错位置,导致路径混乱。map 数组占位不能少:下标 0 和 1 必须留成占位。如果从abc开始填,ch - 0算出的下标就会整体错位一位。可复用模板回溯的多层多分支枚举通用框架(笛卡尔积 / 字符串枚举型),本题和括号生成、字母大小写全排列等都可套用:javaclass Solution { private static final String[] MAP {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; private final ListString res new ArrayList(); public ListString letterCombinations(String digits) { if (digits null || digits.isEmpty()) return res; // ① 空串特判 backtrack(digits, 0, new StringBuilder()); return res; } // 模板:回溯 终止判断(叶子收集) 取当前层候选集 循环 选/递归/撤销 private void backtrack(String digits, int index, StringBuilder path) { if (index digits.length()) { // ② 走到叶子才收集 res.add(path.toString()); // ③ 拷贝,别存引用 return; } String letters MAP[digits.charAt(index) - 0]; // ④ 当前层候选集 for (char c : letters.toCharArray()) { // ⑤ 多分支 path.append(c); // 选 backtrack(digits, index 1, path); // 递归 path.deleteCharAt(path.length() - 1); // 撤销 } } }变体提示:候选集来自每层不同集合→ 用MAP[...]这样按层取;来自同一集合且不可重复用→ 用start参数;来自同一集合可重复用→ 每层都从 0 开始。需要剪枝(如括号生成)→ 在递归入口加约束判断,不满足直接 return。相似题及区别LeetCode 78 子集:二叉决策树,每层 2 分支,且每个节点都是答案;本题是多叉决策树,每层分支数由数字决定,只有叶子才是答案。LeetCode 46 全排列:也是回溯构建完整排列,但每层候选集相同(整个数组),需要boolean[] used去重;本题每层候选集不同(由digits[index]决定),天然不会重复。LeetCode 22 括号生成:同样是回溯拼接字符串,但加入了左括号数 n、右括号数 左括号数的剪枝;本题无剪枝,纯枚举。LeetCode 39 组合总和:回溯 排序剪枝,候选元素可重复使用;本题每个数字只对应固定候选且每层各用一次,不涉及重用问题。