今日算法（组合问题）（回溯解法）
题目描述
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。 数字到字母的映射与电话按键相同，1 不对应任何字母。
示例 1：
- 输入：
digits = "23" - 输出：
["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
- 输入：
digits = "2" - 输出：
["a","b","c"]
解法一：回溯法（递归）
核心思路
这道题本质上是多叉树的深度优先搜索（DFS）。
- 每个数字对应一组字母，相当于树的一层
- 我们需要遍历每一层的所有字母，组合出所有可能的路径
- 当路径长度等于输入数字的长度时，就得到了一个有效组合
代码实现（C++）
class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.empty()) return res; // 数字到字母的映射表 unordered_map<char, string> phoneMap = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; string path; // 保存当前路径 backtrack(digits, 0, phoneMap, path, res); return res; } private: // index：当前处理到第几个数字 void backtrack(const string& digits, int index, const unordered_map<char, string>& phoneMap, string& path, vector<string>& res) { // 终止条件：路径长度等于数字长度 if (index == digits.size()) { res.push_back(path); return; } // 获取当前数字对应的所有字母 char digit = digits[index]; const string& letters = phoneMap.at(digit); // 遍历所有可能的字母 for (char letter : letters) { // 1. 选择当前字母 path.push_back(letter); // 2. 递归处理下一个数字 backtrack(digits, index + 1, phoneMap, path, res); // 3. 回溯：撤销选择，尝试下一个字母 path.pop_back(); } } };详细步骤解析
以输入"23"为例，模拟回溯过程：
- 初始状态：
path = ""，index = 0（处理第一个数字'2'） - 处理数字
'2'，对应字母"abc"：- 选
'a'：path = "a"，递归处理下一个数字index=1- 处理数字
'3'，对应字母"def"：- 选
'd'：path = "ad"，长度等于 2，加入结果集 - 选
'e'：path = "ae"，加入结果集 - 选
'f'：path = "af"，加入结果集
- 选
- 回溯：
path = "a"
- 处理数字
- 选
'b'：path = "b"，递归处理下一个数字，生成"bd", "be", "bf" - 选
'c'：path = "c"，递归处理下一个数字，生成"cd", "ce", "cf"
- 选
- 最终结果：所有组合都已加入
res，返回结果集。
复杂度分析
- 时间复杂度：\(O(3^N \times 4^M)\)
N是对应 3 个字母的数字个数（2,3,4,5,6,8）M是对应 4 个字母的数字个数（7,9）
- 空间复杂度：\(O(N+M)\)
- 递归栈深度等于输入数字的长度，路径
path的最大长度也为N+M
- 递归栈深度等于输入数字的长度，路径
解法二：迭代法（队列模拟）
核心思路
用队列模拟组合的生成过程，每次取出队列中已有的组合，与当前数字的所有字母拼接，生成新的组合，再放回队列。
代码实现（C++）
class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.empty()) return res; // 数字到字母的映射表 vector<string> phoneMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; queue<string> q; q.push(""); // 初始空字符串 for (char digit : digits) { int levelSize = q.size(); // 当前队列中的组合数量 string letters = phoneMap[digit - '0']; // 处理当前层的所有组合 for (int i = 0; i < levelSize; ++i) { string current = q.front(); q.pop(); // 拼接当前数字的所有字母，生成新组合 for (char letter : letters) { q.push(current + letter); } } } // 队列中剩余的元素就是所有组合 while (!q.empty()) { res.push_back(q.front()); q.pop(); } return res; } };详细步骤解析
同样以输入"23"为例：
- 初始状态：队列
q = [""] - 处理数字
'2'（对应"abc"）：- 取出
""，拼接"a", "b", "c"，得到"a", "b", "c"，放回队列 - 队列变为：
["a", "b", "c"]
- 取出
- 处理数字
'3'（对应"def"）：- 取出
"a"，拼接"d", "e", "f"→"ad", "ae", "af"，放回队列 - 取出
"b"，拼接"d", "e", "f"→"bd", "be", "bf"，放回队列 - 取出
"c"，拼接"d", "e", "f"→"cd", "ce", "cf"，放回队列 - 队列变为：
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
- 取出
- 遍历队列，得到最终结果。
两种解法对比
表格
| 对比维度 | 回溯法（递归） | 迭代法（队列） |
|---|---|---|
| 代码简洁度 | 更直观，逻辑清晰 | 稍复杂，需要手动维护队列 |
| 理解难度 | 符合人类思维，容易理解 | 需要理解组合生成的过程 |
| 空间复杂度 | 递归栈深度为数字长度 | 队列需要存储中间结果 |
| 适用场景 | 数字长度不大时（本题长度≤4） | 无递归深度限制，适合所有场景 |
总结
- 这道题是回溯算法的入门经典题，核心是理解 “选择 - 递归 - 回溯” 的过程。
- 回溯法的关键是：用一个路径变量保存当前组合，递归处理每一层，处理完后撤销选择。
- 迭代法是回溯法的非递归实现，用队列模拟组合的生成过程，避免了递归栈溢出的风险。