电话号码的字母组合

问题拆解

九宫格键盘上，每个数字键映射几个字母（2 -> abc、3 -> def……），给一串数字，输出所有可能的字母组合。比如 "23" 的答案是 ad, ae, af, bd, be, bf, cd, ce, cf——第一位从 abc 里挑一个，第二位从 def 里挑一个，组合数是各组大小的乘积，本质是若干个小集合的笛卡尔积。

如果数字串长度固定，写几层嵌套循环就完了；可长度不定，循环的层数没法写死。回溯解决的正是“层数由输入决定的嵌套循环”：用递归深度代替循环层数，每层负责一个数字位，枚举它的所有候选字母，拼上后进入下一层，走到底就收集一条结果。

递归树的第 k 层展开第 k 个数字的字母，一条根到叶的路径就是一个组合。回溯没有什么神秘的，它只是把不定层数的 for 循环写成了递归。

最容易踩的坑在空输入：digits 为空时应返回空列表 []，而不是含一个空串的 [""]。若不加特判，递归第一步就命中“拼完所有位”的收集条件，把空串收进去。

按位递归拼接

映射表用一个按下标访问的数组即可（下标 0、1 空着），比哈希表更直接。路径用可变缓冲区维护，进入下一层前追加一个字母，返回后弹掉，保证同层兄弟分支互不污染。

public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    if (digits.isEmpty()) return res; // 空输入返回空列表，而不是 [""]
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    StringBuilder path = new StringBuilder();
    dfs(digits, 0, map, path, res);
    return res;
}

private void dfs(String digits, int i, String[] map, StringBuilder path, List<String> res) {
    if (i == digits.length()) { // 每一位都选好了
        res.add(path.toString());
        return;
    }
    for (char c : map[digits.charAt(i) - '0'].toCharArray()) {
        path.append(c);
        dfs(digits, i + 1, map, path, res);
        path.deleteCharAt(path.length() - 1); // 回溯：撤销本层选择
    }
}

def letterCombinations(digits: str) -> list[str]:
    if not digits:  # 空输入返回空列表，而不是 [""]
        return []
    mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    res, path = [], []

    def dfs(i: int) -> None:
        if i == len(digits):  # 每一位都选好了
            res.append("".join(path))
            return
        for c in mapping[int(digits[i])]:
            path.append(c)
            dfs(i + 1)
            path.pop()  # 回溯：撤销本层选择

    dfs(0)
    return res

func letterCombinations(digits string) []string {
    if digits == "" { // 空输入返回空列表，而不是 [""]
        return []string{}
    }
    mapping := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    res := []string{}
    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 _, c := range []byte(mapping[digits[i]-'0']) {
            path = append(path, c)
            dfs(i + 1)
            path = path[:len(path)-1] // 回溯：撤销本层选择
        }
    }
    dfs(0)
    return res
}

pub fn letter_combinations(digits: String) -> Vec<String> {
    if digits.is_empty() { // 空输入返回空列表，而不是 [""]
        return vec![];
    }
    const MAP: [&str; 10] = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    let digits: Vec<usize> = digits.bytes().map(|b| (b - b'0') as usize).collect();
    let mut res = Vec::new();
    let mut path = String::new();

    fn dfs(digits: &[usize], i: usize, path: &mut String, res: &mut Vec<String>) {
        if i == digits.len() { // 每一位都选好了
            res.push(path.clone());
            return;
        }
        for c in MAP[digits[i]].chars() {
            path.push(c);
            dfs(digits, i + 1, path, res);
            path.pop(); // 回溯：撤销本层选择
        }
    }
    dfs(&digits, 0, &mut path, &mut res);
    res
}

三个位置容易出错。一是前面说的空输入特判；二是“撤销”必须与“追加”严格配对——漏掉 pop，前一个分支的字母会残留在路径里，后续组合全部错位；三是收集结果时要拷贝一份（toString / join / clone），直接把可变缓冲区塞进结果列表，后面的回溯会把已收集的答案改掉。

复杂度

指标	复杂度	原因
时间	`O(n · 4ⁿ)`	组合最多 4ⁿ 个（7、9 各有四个字母），每个组合拼接花 O(n)
空间	`O(n)`	递归深度与路径缓冲区，均为数字串长度（不计输出）

可以迁移的模式

层数不定的嵌套枚举，用递归深度换循环层数，这是回溯的原始形态；
“路径缓冲区 + 进入前追加、返回后撤销”的配对动作是回溯的手型，收集时记得拷贝；
候选集固定且以小整数索引时，数组映射表比哈希表更简洁。

这道题没有剪枝、没有去重，是回溯框架最干净的样板；组合、子集、全排列都只是在这个骨架上增删收集条件与枚举范围。