【笔面试算法学习专栏】回溯算法困难两题精讲：电话号码的字母组合与括号生成

前言回溯算法Backtracking是算法领域中最经典的问题求解范式之一它通过系统性地枚举所有可能的解空间结合剪枝策略来避免无效搜索。在LeetCode的困难题中有两道经典题目——17. 电话号码的字母组合和22. 括号生成——它们看似简单却蕴含着回溯算法的核心思想与卡特兰数的重要数学原理。本文将深入剖析这两道题目的解题思路、时间空间复杂度分析以及多种解法的对比帮助读者真正掌握回溯算法的精髓。一、LeetCode 17电话号码的字母组合1.1 题目描述给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。数字到字母的映射与电话按键相同如下所示2 - abc 3 - def 4 - ghi 5 - jkl 6 - mno 7 - pqrs 8 - tuv 9 - wxyz示例输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]1.2 问题分析本题的核心在于组合生成每个数字对应一组字母需要在所有可能字母中进行笛卡尔积组合。以输入23为例数字2对应字母[a, b, c]数字3对应字母[d, e, f]组合结果每个2的字母后接每个3的字母这个问题可以用树状结构来理解——每层代表一个数字对应的字母选择叶子节点代表一种完整的组合。1.3 回溯法解题思路回溯法是解决此问题的最直观方法。其核心思想是从第一位数字开始遍历所有可能的字母对每一个字母递归处理下一个数字直到组合长度等于输入数字串长度时将结果加入列表回溯三部曲① 确定回溯函数参数digits输入的数字字符串index当前遍历到的数字位置② 确定终止条件当index len(digits)时说明已经处理完所有数字将当前路径加入结果③ 单层遍历逻辑获取当前数字对应的字母集合遍历每个字母选择后递归递归后回溯撤销选择1.4 代码实现fromtypingimportListclassSolution:defletterCombinations(self,digits:str)-List[str]:ifnotdigits:return[]# 数字到字母的映射phoneMap{2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz}result[]defbacktrack(index:int,path:List[str]):# 终止条件处理完所有数字ifindexlen(digits):result.append(.join(path))return# 获取当前数字对应的字母lettersphoneMap[digits[index]]forletterinletters:path.append(letter)# 选择backtrack(index1,path)# 递归path.pop()# 回溯backtrack(0,[])returnresult1.5 复杂度分析复杂度分析时间复杂度O(3m×4n)O(3^m \times 4^n)O(3m×4n)其中m是3字母数字的数量n是4字母数字7和9的数量空间复杂度O(n)O(n)O(n)递归栈深度n为数字长度不计输出结果空间1.6 迭代法非递归解法除了回溯我们还可以使用迭代的队列方法defletterCombinations_iterative(digits:str)-List[str]:ifnotdigits:return[]phoneMap{2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz}result[]fordigitindigits:result[prevletterforprevinresultforletterinphoneMap[digit]]returnresult这种方法利用列表推导式每次扩展一层时间复杂度相同但代码更简洁。二、LeetCode 22括号生成2.1 题目描述数字 n 代表生成括号的对数请你设计一个函数用于生成所有可能的并且有效的括号组合。示例输入n 3输出[((())),(()()),(())(),()(()),()()()]2.2 问题分析括号生成问题的核心在于有效性的约束左括号和右括号数量相等各为n个任意前缀中左括号数量不小于右括号数量否则会出现)(这样的无效情况生成的括号序列数量是卡特兰数Cn1n1(2nn)4nnπnC_n \frac{1}{n1}\binom{2n}{n} \frac{4^n}{n\sqrt{\pi n}}Cn​n11​(n2n​)nπn​4n​对于n8序列数量为1430在可接受范围内。2.3 回溯法解法使用DFS回溯的核心思想跟踪当前已使用的左括号和右括号数量只有左括号数量小于n时才能添加左括号只有右括号数量小于左括号数量时才能添加右括号classSolution:defgenerateParenthesis(self,n:int)-List[str]:result[]defbacktrack(current:str,left:int,right:int):# 终止条件左右括号都用完iflen(current)2*n:result.append(current)return# 添加左括号的条件ifleftn:backtrack(current(,left1,right)# 添加右括号的条件右括号数 左括号数ifrightleft:backtrack(current),left,right1)backtrack(,0,0)returnresult2.4 动态规划卡特兰构造任何有效括号序列都可以分解为(A)B的形式其中A和B是更小的有效括号序列。这引出了卡特兰递推dp[k]⋃i0k−1(dp[i])dp[k−1−i]dp[k] \bigcup_{i0}^{k-1} ( dp[i] ) dp[k-1-i]dp[k]i0⋃k−1​(dp[i])dp[k−1−i]defgenerateParenthesis_dp(n:int)-List[str]:dp[[]for_inrange(n1)]dp[0][]forkinrange(1,n1):foriinrange(k):forleftindp[i]:forrightindp[k-1-i]:dp[k].append((left)right)returndp[n]2.5 复杂度分析解法时间复杂度空间复杂度特点回溯法O(4nn)O(\frac{4^n}{\sqrt{n}})O(n​4n​)O(n)O(n)O(n)只生成有效解代码简洁动态规划O(Cn⋅n2)O(C_n \cdot n^2)O(Cn​⋅n2)O(Cn⋅n)O(C_n \cdot n)O(Cn​⋅n)揭示卡特兰结构常数较大暴力法O(22n⋅n)O(2^{2n} \cdot n)O(22n⋅n)O(22n⋅n)O(2^{2n} \cdot n)O(22n⋅n)先生成后验证不推荐三、卡特兰数详解3.1 卡特兰数的定义卡特兰数是组合数学中常见的一个重要数列其前几项为1,1,2,5,14,42,132,429,1430,4862,…1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \ldots1,1,2,5,14,42,132,429,1430,4862,…通项公式Cn1n1(2nn)(2n)!(n1)!n!C_n \frac{1}{n1}\binom{2n}{n} \frac{(2n)!}{(n1)!n!}Cn​n11​(n2n​)(n1)!n!(2n)!​3.2 卡特兰数的应用场景括号匹配n对括号的有效组合数二叉树计数n1个叶子的不同二叉树数量栈操作合法进栈出栈序列数凸多边形三角剖分** Dyck路径**不穿过对角线的网格路径数3.3 卡特兰数的递推关系卡特兰数满足以下递推关系C01C_0 1C0​1Cn1∑i0nCi⋅Cn−iC_{n1} \sum_{i0}^{n} C_i \cdot C_{n-i}Cn1​i0∑n​Ci​⋅Cn−i​这个递推关系正是括号生成DP解法的数学基础。四、回溯算法通用模板4.1 回溯法的基本框架defbacktrack(路径,选择列表):if满足结束条件:结果.append(路径)returnfor选择in选择列表:# 做选择路径.append(选择)# 递归backtrack(路径,新选择列表)# 撤销选择回溯路径.pop()4.2 回溯法的适用场景场景典型题目组合问题组合总和、子集排列问题全排列、字母排列切割问题复原IP地址、分割回文串子集问题递增子序列棋盘问题N皇后、数独4.3 剪枝优化策略提前终止当已知无法得到有效解时提前返回约束剪枝根据问题约束排除不可能的选择去重剪枝对于需要去重的问题使用visited集合或排序跳过相同元素五、面试要点总结5.1 关键问题Q为什么有效括号序列的数量是卡特兰数A可以将问题转化为从(0,0)到(n,n)的路径问题要求不穿过对角线。这样的路径数就是卡特兰数。直观理解总路径数为(2nn)\binom{2n}{n}(n2n​)减去穿过对角线的路径映射为Catalan数得到CnC_nCn​。Q如果n很大如n20算法如何优化A对于大n生成所有序列不现实。如果只需要数量可以用卡特兰数公式直接计算。如果需要部分序列可以使用随机生成验证的方法。Q电话号码组合问题的时间复杂度为什么是3m×4n3^m \times 4^n3m×4nA每个3字母数字2,3,4,5,6,8贡献3种选择每个4字母数字7,9贡献4种选择。假设有m个3字母数字和n个4字母数字总组合数为3m×4n3^m \times 4^n3m×4n。5.2 面试首选方案对于括号生成问题回溯优化法是面试首选因为它展示对递归和剪枝的掌握代码简洁性能优秀易于扩展如要求返回数量而非列表5.3 代码风格建议# 推荐清晰的结构和注释defbacktrack(self,pos:int,path:List[str],res:List[str]):ifposlen(path):res.append(.join(path))return# ...具体逻辑# 避免过于简洁导致可读性差defbacktrack(pos,path):ifposlen(path):res.append(.join(path));return六、总结本文深入剖析了两道经典的回溯算法困难题电话号码的字母组合展示了集合间组合的回溯模式时间复杂度O(3m×4n)O(3^m \times 4^n)O(3m×4n)括号生成展示了带约束的组合生成引入了卡特兰数的概念时间复杂度O(4nn)O(\frac{4^n}{\sqrt{n}})O(n​4n​)这两道题的共同点在于都使用DFS回溯遍历解空间都通过剪枝避免无效搜索都需要理解问题的数学本质掌握这些核心思想可以帮助我们解决更广泛的回溯问题。参考文献LeetCode. (2024). 17. 电话号码的字母组合. https://leetcode.cn/problems/letter-combinations-of-a-phone-number/LeetCode. (2024). 22. 括号生成. https://leetcode.cn/problems/generate-parentheses/Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4), 229-256.