17. 电话号码的字母组合
这题是经典的回溯（Backtracking）入门题。
核心思想：
每个数字都对应几个字母
我们要从每一位数字里“选一个字母”
一直选到最后，就得到一个完整组合
比如：
"23" 2 -> abc 3 -> def其实就是：
a + d a + e a + f b + d ...本质上是一棵树：
"" / | \ a b c / | \ ... d e f回溯模板思路
回溯三件套：
1. 路径 path 2. 选择列表 3. 结束条件这里：
path = 当前拼出的字符串 选择列表 = 当前数字对应的字母 结束条件 = path长度 == digits长度标准解法（推荐背下来）
class Solution { List<String> res = new ArrayList<>(); String[] map = { "", // 0 "", // 1 "abc", // 2 "def", // 3 "ghi", // 4 "jkl", // 5 "mno", // 6 "pqrs", // 7 "tuv", // 8 "wxyz" // 9 }; public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return res; } backtrack(digits, 0, new StringBuilder()); return res; } public void backtrack(String digits, int index, StringBuilder path) { // 结束条件 if (index == digits.length()) { res.add(path.toString()); return; } // 当前数字 char digit = digits.charAt(index); // 转成 int String letters = map[digit - '0']; // 遍历当前数字对应字母 for (char c : letters.toCharArray()) { // 做选择 path.append(c); // 递归下一层 backtrack(digits, index + 1, path); // 撤销选择 path.deleteCharAt(path.length() - 1); } } }一步一步理解执行过程
以：
digits = "23"开始：
第一层：
index = 0 letters = abc选择：
a b c假设先选：
a进入第二层：
index = 1 letters = def继续选：
d e f得到：
ad ae af然后回退。
再选：
b得到：
bd be bf为什么需要“撤销选择”？
这是回溯最核心的地方。
比如：
path.append(c);加入了：
a递归结束后，必须删掉：
path.deleteCharAt(path.length() - 1);否则下一轮会变成：
ad -> ade路径会污染。
时间复杂度
每个数字最多 4 个字母。
假设长度是 n：
时间复杂度：O(4^n)因为本质是枚举所有组合。
这题真正训练的东西
这题非常重要，因为它是：
回溯树模型的起点
以后这些题本质都一样：
全排列
子集
组合
N皇后
括号生成
单词搜索
你会发现：
做选择 递归 撤销选择永远都是这一套。
这题你如果已经理解了，我下一题建议你直接做：
22 括号生成
46 全排列
因为它们会让你真正掌握回溯树。