电话号码的字母组合如何用回溯生成？递归状态怎么定义？

简化版

电话号码字母组合用回溯按位生成：递归参数 index 表示处理到第几个数字，path 保存当前组合；每层根据当前数字映射到 3 或 4 个字母，逐个选择、递归到下一位、再撤销。index == digits.length() 时收集一个完整字符串。

详细版

这题的搜索树很清楚：输入有几位数字，递归树就有几层；每一层的分支数等于该数字对应的字母数。比如 "23"，第一层可选 a,b,c，第二层可选 d,e,f，共 3 * 3 = 9 个组合。

实现时先建立数字到字母的映射，如 2 -> "abc"、7 -> "pqrs"。如果输入为空，直接返回空列表。递归函数处理第 index 位数字，把每个候选字母加入 path，递归 index + 1，返回后删除最后一个字符。

复杂度是输出规模级别。若长度为 n，每位最多 4 个字母，组合数最多 4^n，复制每个答案需要 O(n)，总时间可写为 O(n * 4^n)，空间为递归深度 O(n) 加输出空间。

完整版教学

一、为什么这题是典型回溯

电话号码字母组合不是在找最短路或最优值，而是在枚举所有合法组合。每一位数字必须选一个字母，前面选了什么会和后面拼成一个完整字符串。这正是回溯的“路径 + 当前层选择列表 + 结束条件”模型。

例如 digits = "23"：第 0 层处理数字 2，可选 a,b,c；第 1 层处理数字 3，可选 d,e,f。一条从根到叶子的路径 a -> d 就对应答案 "ad"。

        ""
    /    |    \
   a     b     c
 / | \ / | \ / | \
ad ae af bd be bf cd ce cf

二、递归状态如何定义

递归函数只需要两个状态：index 和 path。index 表示当前要处理 digits 的哪一位；path 表示前面已经选好的字母序列。当 index == digits.length()，说明每一位都选完了，path 就是一个完整答案。

这个状态定义比“传剩余字符串”更稳定，因为下标天然表示层数，不需要频繁切片。对于输入 "279"，树深是 3：第 0 层分支 3 个，第 1 层分支 4 个，第 2 层分支 4 个，总组合数是 3 * 4 * 4 = 48。

记忆钩子：这题的 index 就是“正在填第几个格子”，path 就是“已经填好的前缀”。

三、代码模板

用 StringBuilder 或字符数组维护路径都可以。Java 里用 StringBuilder 时，递归后要 deleteCharAt(length - 1) 撤销选择。

List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    if (digits == null || digits.length() == 0) return res;
    String[] map = {
        "", "", "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };
    backtrack(digits, 0, map, new StringBuilder(), res);
    return res;
}

void backtrack(String digits, int index, String[] map, StringBuilder path, List<String> res) {
    if (index == digits.length()) {
        res.add(path.toString());
        return;
    }
    String letters = map[digits.charAt(index) - '0'];
    for (char ch : letters.toCharArray()) {
        path.append(ch);
        backtrack(digits, index + 1, map, path, res);
        path.deleteCharAt(path.length() - 1);
    }
}

这里没有去重，也没有剪枝，因为每条长度为 n 的路径都是合法答案，必须完整枚举。

四、复杂度来自乘法原理

每位数字有 3 或 4 个候选字母。若输入长度为 n，最坏情况下每位都是 7 或 9，对应 4 个字母，答案数就是 4^n。生成每个字符串需要复制长度 n 的路径，所以输出成本是 O(n * 4^n)。

输入	分支数	组合数
`"23"`	`3 * 3`	9
`"279"`	`3 * 4 * 4`	48
`"7777"`	`4^4`	256

面试里要强调：这不是算法不够优化，而是题目要求输出所有组合，输出本身就这么大。

五、和排列、组合题的区别

电话号码组合不需要 used[]，因为每层选择的是当前数字映射出来的字母，不存在“某个输入元素是否已被使用”的问题。它也不需要 start，因为每一层的候选集合由固定位置的数字决定，不是从数组后缀里挑。

题型	控制变量	候选来源
电话号码字母组合	`index`	当前数字对应字母
全排列	`used[]`	所有未使用元素
子集/组合	`start`	当前下标之后的元素

这个对比能帮助你在回溯题里快速选模板，而不是所有题都套同一个 start。

六、常见误区与追问

误区：空输入返回包含空串的列表。 常见题意要求空输入返回空列表，而不是 [""]。
误区：忘记撤销 StringBuilder。 不删除最后一个字符，后续分支会带着前一个分支的状态。
误区：把 7 和 9 也写成 3 个字母。 7 -> pqrs、9 -> wxyz 都是 4 个字母。
追问：能不能用 BFS 队列做？ 可以逐位扩展已有前缀，本质仍是按层枚举所有组合。
追问：复杂度为什么不是 O(4^n) 就完了？ 若计入构造答案字符串，每个答案复制长度 n，因此是 O(n * 4^n)。
追问：如何避免 StringBuilder 回溯错误？ 可用固定长度 char 数组，写 chars[index]=ch，到叶子再 new String。

七、加强记忆

电话号码字母组合记成“一位数字一层树，一个字母一条边”。index 控制层数，path 保存前缀，走到 index == n 就收集答案。它不用 start、不用 used[]、不用剪枝，关键是映射准确和撤销干净。

简化版

详细版