现在的HR不直接说 35岁不要，但筛选逻辑变了，35岁+普通公司+薪资20k>几乎收不到面试邀请。

昨天晚上十一点多，我在公司楼下便利店买泡面，排队的时候无聊刷手机，看到群里有人又在刷 LeetCode，那道“电话号码的字母组合”。 小李直接一句：哥，这题为啥一看就觉得简单，一写就乱成一锅粥？

我当时困得要死，但脑子一想，这题其实特别适合讲“回溯”这个事，就顺手在手机备忘录里敲了个 Java 版本，第二天稍微整理了下，就有了这篇啰嗦分享。

老旧那种按键手机你见过吧，数字 2–9 每个键下面都印着几个字母，比如：

• 2 -> abc
• 3 -> def
• 4 -> ghi
• ……
• 9 -> wxyz

给你一个只包含 2–9 的数字串，比如 "23"，让你把所有可能的字母组合都列出来："23" 就可以按成：ad、ae、af、bd、be、bf、cd、ce、cf 这些。

看着就像枚举所有可能对吧，其实就是暴力搜索，只是写法上容易绕。

你现在有一串数字，假设是 "27"。那你要做的事情就是——

1. 先在 2 的字母里选一个（a / b / c 里挑一个）
2. 再在 7 的字母里选一个（p / q / r / s 里挑一个）
3. 每次选完一整串（长度等于 digits 长度）就存起来

你会发现这个过程特别像在一棵多叉树上“深度优先”往下走：

• 每一层代表一个数字
• 这一层的每个分支代表这个数字上的一个字母
• 走到第 n 层（数字串长度）就得到一个完整的组合

程序里就是典型回溯套路：

• path：当前已经选了哪些字母
• index：现在处理到第几位数字
• 选一个字母 -> 继续递归下一位 -> 回退这个字母，换下一个

我直接把 Java 源码扔出来，你们一边看一边对照我上面说的那个“往下走的树”就行：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

publicclassSolution{

// 数字到字母的映射
privatestaticfinal Map<Character, String> PHONE_MAP = new HashMap<>();
static {
        PHONE_MAP.put('2', "abc");
        PHONE_MAP.put('3', "def");
        PHONE_MAP.put('4', "ghi");
        PHONE_MAP.put('5', "jkl");
        PHONE_MAP.put('6', "mno");
        PHONE_MAP.put('7', "pqrs");
        PHONE_MAP.put('8', "tuv");
        PHONE_MAP.put('9', "wxyz");
    }

private List<String> result = new ArrayList<>();
private StringBuilder path = new StringBuilder();

public List<String> letterCombinations(String digits){
// 边界情况：空串直接返回空列表
if (digits == null || digits.length() == 0) {
return result;
        }
        backtrack(digits, 0);
return result;
    }

// 回溯函数：index 表示当前处理到 digits 的第几位
privatevoidbacktrack(String digits, int index){
// 说明一条路径已经选完了，长度 == digits 长度
if (index == digits.length()) {
            result.add(path.toString());
return;
        }

char digit = digits.charAt(index);
        String letters = PHONE_MAP.get(digit);
if (letters == null) {
// 理论上不会走到这，保险写一下
return;
        }

// 在当前数字对应的所有字母里，一个个尝试
for (int i = 0; i < letters.length(); i++) {
char ch = letters.charAt(i);

// 选择：把当前字母加到路径里
            path.append(ch);

// 继续走下一层，也就是下一个数字
            backtrack(digits, index + 1);

// 撤销选择：删掉刚刚加的这个字母
            path.deleteCharAt(path.length() - 1);
        }
    }
}

你可以脑补一下 "23" 的执行过程：

• 第一步选 2 上的 a，path = "a"
• 然后去选 3 上的 d，path = "ad"，长度够了，收集
• 回退到 path = "a"，再选 e -> "ae"，再选 f -> "af"
• 然后整层回退，删掉 a，变回空串 ""
• 再选 b，重复上面的流程……

反正就是“选一个 -> 递归 -> 回退 -> 换下一个”，干到所有数字都处理完。

有人在群里问了一嘴性能问题，我顺便也说下，别被面试官问懵了：

• 假设 digits 长度是 n

• 每个数字平均 3、4 个字母，那总组合数量大概就是 3ⁿ 或 4ⁿ 这个量级

• 每产生一个组合要拷贝一次字符串，所以总时间差不多就是 O(kⁿ) 这种指数级（k 取 3~4），这题本来就是这样，没法再优化到多恐怖

• 空间上主要是：

• 递归深度 O(n)
• path 长度 O(n)
• 加上结果列表本身（这个是题目要求产出的，不能算浪费）

所以这题考的不是“更牛的算发”，考的是你回溯套路写得熟不熟，边界条件清不清楚，代码干不干净。

顺嘴再提一个思路，面试的时候有时候我会聊一下“非递归”的版本，其实就是：

• 先有一个列表，里面先放一个空串 [""]
• 每读到一个新数字，就把旧列表里每个字符串，跟这个数字的所有字母拼上去，生成一个新列表
• 把旧列表扔掉，新列表顶上去
• 直到所有数字处理完

这个更像 BFS 层层扩散，写出来也不难，就是代码比回溯长点，我一般只说思路就够用了，免得白写那么多字面试官还不看，气人。