京公网安备11010502063487号手机九宫格键盘上，数字 2 到 9 各对应几个字母（2 对应 abc，7 对应 pqrs，依此类推）。给定一个由 2 到 9 组成的数字串，返回它能表示的所有字母组合，顺序不限。这是回溯的入门题：每一位从它对应的字母里选一个，选完一位递归到下一位，走到底就收集一个结果，返回时撤销选择。结果的个数是各位字母数的乘积，本身就是指数级的，所以这道题的重点不在优化，而在写对：空输入怎么处理、撤销选择有没有漏。本文实测结果规模的增长，展示空字符串的陷阱，给出五种语言的实现，并把递归和回溯过程做成分步演示。
完整题目见官方页面（链接在文末）。数字串可以为空，为空时返回空列表。基准解用 Python 的 itertools.product 直接求各位字母集合的笛卡尔积，与回溯是两种独立写法。一共 12 组用例，覆盖：官方示例 "23"、空串、单个数字、含 4 个字母的 7 和 9、重复数字、长度 4：
输入 ["23"] 输出 ["ad","ae","af","bd","be","bf","cd","ce","cf"] 输入 [""] 输出 [] 输入 ["2"] 输出 ["a","b","c"] 输入 ["7"] 输出 ["p","q","r","s"] 输入 ["79"] 输出 ["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"] 输入 ["234"] 输出 ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]
回溯的写法里，"走到最后一位就收集当前路径"。输入为空时，一开始就满足"走到最后一位"，路径是空串，于是收集了一个空字符串，返回 [""]。但题目要求这种情况返回 []。下面是真实结果：
空字符串：没有特判的回溯 -> [''] solve -> []
没有特判的回溯返回了含一个空字符串的列表，solve 在入口处对空输入直接返回空列表。五种语言的实现都加了这个特判。
dfs(i) 表示正在处理第 i 位。当 i 等于数字串长度时收集当前路径；否则依次尝试这一位对应的每个字母：把字母加入路径，递归到下一位，再把它从路径里去掉。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；Java 用 StringBuilder 加 deleteCharAt，Go 用字节切片再截短，C++ 用 string 的 push_back 和 pop_back。
Python · 解法代码PHONE = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"} def solve(digits): if not digits: # 空输入要返回 []，而不是 [""] return [] res, path = [], [] def dfs(i): if i == len(digits): res.append("".join(path)) return for ch in PHONE[digits[i]]: path.append(ch) dfs(i + 1) path.pop() # 回溯：撤销这一步选择 dfs(0) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["23"] → ["ad","ae","af","bd","be","bf","cd","ce","cf"] [""] → [] ["2"] → ["a","b","c"] ["7"] → ["p","q","r","s"] ["79"] → ["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"] ["234"] → ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]
Java · 解法代码class Solution { private static final String[] PHONE = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public List<String> letterCombinations(String digits) { List<String> res = new ArrayList<>(); if (digits.isEmpty()) return res; // 空输入要返回 []，而不是 [""] dfs(digits, 0, new StringBuilder(), res); return res; } private void dfs(String digits, int i, StringBuilder path, List<String> res) { if (i == digits.length()) { res.add(path.toString()); return; } for (char ch : PHONE[digits.charAt(i) - '0'].toCharArray()) { path.append(ch); dfs(digits, i + 1, path, res); path.deleteCharAt(path.length() - 1); // 回溯：撤销这一步选择 } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["23"] → ["ad","ae","af","bd","be","bf","cd","ce","cf"] [""] → [] ["2"] → ["a","b","c"] ["7"] → ["p","q","r","s"] ["79"] → ["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"] ["234"] → ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]
Go · 解法代码var phone = [...]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"} func letterCombinations(digits string) []string { res := []string{} if len(digits) == 0 { // 空输入要返回 []，而不是 [""] return res } path := make([]byte, 0, len(digits)) var dfs func(i int) dfs = func(i int) { if i == len(digits) { res = append(res, string(path)) return } for _, ch := range []byte(phone[digits[i]-'0']) { path = append(path, ch) dfs(i + 1) path = path[:len(path)-1] // 回溯：撤销这一步选择 } } dfs(0) return res }
$ go build -o bin . && ./bin < cases.jsonl ["23"] → ["ad","ae","af","bd","be","bf","cd","ce","cf"] [""] → [] ["2"] → ["a","b","c"] ["7"] → ["p","q","r","s"] ["79"] → ["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"] ["234"] → ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]
JavaScript · 解法代码const PHONE = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]; function letterCombinations(digits) { const res = []; if (digits.length === 0) return res; // 空输入要返回 []，而不是 [""] const path = []; const dfs = (i) => { if (i === digits.length) { res.push(path.join("")); return; } for (const ch of PHONE[Number(digits[i])]) { path.push(ch); dfs(i + 1); path.pop(); // 回溯：撤销这一步选择 } }; dfs(0); return res; }
$ node run.js < cases.jsonl ["23"] → ["ad","ae","af","bd","be","bf","cd","ce","cf"] [""] → [] ["2"] → ["a","b","c"] ["7"] → ["p","q","r","s"] ["79"] → ["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"] ["234"] → ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { const vector<string> PHONE = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void dfs(const string& digits, int i, string& path, vector<string>& res) { if (i == (int)digits.size()) { res.push_back(path); return; } for (char ch : PHONE[digits[i] - '0']) { path.push_back(ch); dfs(digits, i + 1, path, res); path.pop_back(); // 回溯：撤销这一步选择 } } public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.empty()) return res; // 空输入要返回 []，而不是 [""] string path; dfs(digits, 0, path, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["23"] → ["ad","ae","af","bd","be","bf","cd","ce","cf"] [""] → [] ["2"] → ["a","b","c"] ["7"] → ["p","q","r","s"] ["79"] → ["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"] ["234"] → ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
结果个数是每位字母数的乘积，用真实运行的数量验证：
数字串长度 k 与结果个数（全用 2，每位 3 个字母；全用 7，每位 4 个字母） k=1: 全 2 -> 3（3^1=3） 全 7 -> 4（4^1=4） k=2: 全 2 -> 9（3^2=9） 全 7 -> 16（4^2=16） k=3: 全 2 -> 27（3^3=27） 全 7 -> 64（4^3=64） k=4: 全 2 -> 81（3^4=81） 全 7 -> 256（4^4=256） k=5: 全 2 -> 243（3^5=243） 全 7 -> 1024（4^5=1024） k=6: 全 2 -> 729（3^6=729） 全 7 -> 4096（4^6=4096） k=7: 全 2 -> 2187（3^7=2187） 全 7 -> 16384（4^7=16384） k=8: 全 2 -> 6561（3^8=6561） 全 7 -> 65536（4^8=65536）
数字全是 2（3 个字母）时个数是 3 的 k 次方，全是 7（4 个字母）时是 4 的 k 次方，每增加一位，个数乘以 3 或 4。下面是数字串长度分别为 4、6、8、10（全是 7 和 9，每位 4 个字母）时，回溯与 itertools.product 的耗时，每个规模取三次中最快的一次：
数字个数（全是 7 和 9，每位 4 个字母） | 暴力解 | 本文解法
4 | 0.017 ms | 0.036 ms
6 | 0.299 ms | 0.612 ms
8 | 5.582 ms | 10.394 ms
10 | 109.881 ms | 181.555 ms耗时随长度大约每增加两位涨 17 到 20 倍，符合每位乘以 4（两位是 16 倍）加上生成字符串的额外开销。本次测量里 itertools.product 版本比手写回溯快，长度 10 时分别是 109.9ms 和 181.6ms，这里我没有做进一步的分析，可能是 Python 函数调用开销较大，这只是猜测。
Python 版本另外和 itertools.product 做了随机对拍，这次要求结果的顺序也完全一致：
随机对拍 3000 组（长度 0 到 6、每位取 2 到 9 的随机数字串（结果的顺序也要完全一致）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，其中每组的输出顺序也和基准完全一致，没有做大规模随机对拍。
下面的演示用 "23"。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示收集到的结果与 solve 的返回值一致。注意"回溯"帧：撤销一个字母后 path 回到上一状态，再尝试下一个字母。