LeetCode 241：分治算法与递归求解表达式所有加括号结果

1. 先看懂题目这个返回值到底长什么样Leetcode 241题为“为运算表达式设计优先级”是分治算法应用里最出名的一道题。它要你做的事情非常直白输入一个只含有数字和 、-、* 三种运算符的字符串你需要把所有可能的加括号方式全部计算一遍并把每一种方式得到的值都放进列表返回。我把这句话再拆开强调一遍不是让你找到“最优”的加括号方式也不是让你算“最大值最小值”而是穷举所有合法分组返回全部结果。这个语气上的差异决定了解题方向完全不同。第一次看到这个题时很多人会下意识往“表达式求值”“运算符优先级”这类常规解析题上靠想着是不是要设计一个带优先级的解析器。但实际上题目已经把“优先级”这个问题彻底交给用户自定义了——每一对括号都是一种优先级声明你要把所有声明方式的结果都枚举出来。这个立意决定了它天然是一个递归枚举问题而不是一个解析优化问题。1.1 两个例子吃透需求第一个例子是2-1-1。两个减号能形成的完整括号结构一共两种((2-1)-1) 0(2-(1-1)) 2所以返回 [0, 2]先后顺序无所谓。第二个例子是2*3-4*5三个运算符完整加括号方式共 5 种我列全给你看(2*(3-(4*5))) -34((23)-(45)) -14((2*(3-4))*5) -10(2*((3-4)*5)) -10(((2*3)-4)*5) 10注意这里 -10 出现了两次一种是把 3-4 先算另一种是把整个左侧先分成 2*3-4 再算。两种不同的括号结构算出了同一个数值这是完全合法的题目明确要求“返回所有可能的结果”重复值必须保留。我在这道题上翻过一次车当时自作聪明在返回前加了个去重操作觉得“结果集里不该有重复数字”结果2*3-4*5只返回了 4 个元素而不是 5 个怎么都过不了。这个教训后面会详细展开这里先记住一个铁律——题目说返回所有结果就是字面意义的“所有”重复值一个都不能少。1.2 结果数量和卡特兰数可能你会问结果最多有多少个这其实是个很有意思的问题。n 个运算符的完整加括号方式数恰好是第 n 个卡特兰数 C(n)C(0)1, C(1)1, C(2)2, C(3)5, C(4)14, C(5)42……公式是 C(n) C(2n, n)/(n1)。卡特兰数的增长是指数级的。这意味着一个残酷的事实这道题的输出本身就是指数级的所以任何解法在最坏情况下都不可能做到多项式时间。理解这一点对后面的复杂度分析非常关键——你别指望有 O(n^2) 级别的解法能输出这些结果那在数学上就不成立。好在题目把字符串长度限制在 20 以内所以最坏情况下运算符个数也就 9 个左右卡特兰数 C(9) 4862暴力递归完全跑得动。这也是为什么这题被归为中等偏易的经典递归题——输入规模恰到好处地落在了“暴力可解”的区间里。2. 为什么天然适合分治运算符就是切分点2.1 分治三件套在本题的落法先回顾一下分治算法的三个标准步骤分解、求解、合并。这道题三个步骤的落法非常清晰简直可以直接对号入座。分解任选表达式中的一个运算符作为切分点把表达式切成“左子串 运算符 右子串”。比如2*3-4*5选中间的 -得到2*3和4*5选第一个 *得到2和3-4*5。为什么可以这么切因为任何一个完整的加括号表达式它的最外层一定也是一个运算符左边是左子表达式的某种加括号方式右边是右子表达式的某种加括号方式。换句话说枚举“最外层运算符是谁”和“左右两半各自怎么加括号”就已经覆盖了所有情况不重不漏。求解左右子串是形式相同、规模更小的同类问题直接递归。递归的出口是子串里已经没有运算符即它就是纯数字此时返回[int(子串)]。合并两个子问题各返回一个结果列表用切分点的运算符做笛卡尔积式的两两组合。比如左列表有 L 个结果、右列表有 R 个结果合并后就产生 L*R 个候选结果。这种“枚举切分点 递归两边 交叉合并”的模式是很多表达式枚举类问题的通用骨架。分治在这里完全不是生搬硬套而是和问题的数学结构严丝合缝。2.2 手推递归树2*3-4*5是怎么长出 5 个结果的光说不练不行我带你完整手推一遍2*3-4*5。主函数会依次把它在每个运算符处切开分三条路递归第一条路切在第一个 左2直接返回 [2]右3-4*5继续分治——右子串切在 - 时左3-[3]、右4*5-[20]合并得 3-20-17切在 时左3-4-[-1]、右5-[5]合并得 -1*5-5。所以3-4*5返回 [-17, -5]。回到顶层2 * (-17) -342 * (-5) -10。生成了 -34 和 -10。第二条路切在 -左2*3返回 [6]右4*5返回 [20]合并得 6-20 -14。生成 -14。第三条路切在最后一个 左2*3-4继续分治——切在 时左2-[2]、右3-4-[-1]合并得 2*(-1)-2切在 - 时左2*3-[6]、右4-[4]合并得 6-42。所以2*3-4返回 [-2, 2]。回到顶层(-2)5 -1025 10。生成 -10 和 10。把三条路的结果汇总[-34, -14, -10, -10, 10]正好和前面枚举的 5 种一致。注意第三条路的第一个结果和第一条路的第二个结果都是 -10它们源自不同括号结构所以都要保留。3. 代码落地递归模板与复杂度分析3.1 Python 实现与逐行解读先看核心递归版本Pythonfrom typing import List def diffWaysToCompute(expression: str) - List[int]: # 边界纯数字直接返回 if expression.isdigit(): return [int(expression)] res [] for i, ch in enumerate(expression): if ch in -*: # 分解按当前运算符切成左右两半 left diffWaysToCompute(expression[:i]) right diffWaysToCompute(expression[i1:]) # 合并左右结果两两运算 for l in left: for r in right: if ch : res.append(l r) elif ch -: res.append(l - r) else: res.append(l * r) return res整段代码的骨架就是刚才说的三步我逐行说几个容易被忽略的细节。expression.isdigit()是最省事的边界判断。它对于12这样的多位数也返回 True所以多位数天然被正确处理不需要额外解析。但注意它只适用于“输入里没有负数”的前提——这道题恰好满足所以是安全的。如果你要拿这个模板去处理带负号的表达式isdigit 会把-5判成 False然后递归就乱了需要额外处理。for i, ch in enumerate(expression)这一步是找到所有运算符的位置对每个运算符都尝试作为“最外层运算符”。这对应着“枚举所有切分点”一个都不能漏。合并阶段用两层 for 循环做笛卡尔积。这里没有去重也没有排序顺序由递归顺序天然决定LeetCode 允许任意顺序返回所以不用管。3.2 Java 实现与“空结果即数字”的写法Java 版本的核心逻辑一模一样但边界处理可以换一种更通用的姿势——“扫描完没有运算符说明是纯数字”class Solution { public ListInteger diffWaysToCompute(String expression) { ListInteger res new ArrayList(); for (int i 0; i expression.length(); i) { char c expression.charAt(i); if (c || c - || c *) { ListInteger left diffWaysToCompute(expression.substring(0, i)); ListInteger right diffWaysToCompute(expression.substring(i 1)); for (int l : left) { for (int r : right) { if (c ) res.add(l r); else if (c -) res.add(l - r); else res.add(l * r); } } } } // 整个循环没进去过说明没有运算符表达式就是单个数字 if (res.isEmpty()) { res.add(Integer.parseInt(expression)); } return res; } }这种res.isEmpty()兜底的方式其实更通用因为它不依赖 isdigit 这类“纯数字判断”以后如果扩展成“表达式里可能带括号”等变体这个写法依然成立。实测下来 Java 这种写法在2*3-4*5上的递归过程和 Python 版本完全一致选哪个顺手就用哪个。3.3 复杂度真的爆炸吗设运算符个数为 m最终结果数为卡特兰数 C(m)。主函数一层要生成 C(m) 个结果而递归过程中所有子问题生成的结果总和也差不多是 C(m) 乘以一个多项式因子。所以时间复杂度和空间复杂度都是 O(C(m))也就是 O(4^m / m^(3/2)) 这个量级的指数复杂度。听上去吓人但回到题目约束字符串长度 ≤ 20m 最多也就 9 左右C(9) 4862实际跑起来是毫秒级。刷题久了你会形成一种直觉指数复杂度的算法不一定不能过关键看输入上限。反而是那种“看起来是 O(n^3) 但 n 是 10^5”的题才是真正需要花心思优化的对象。但话说回来面试时如果面试官追问“这个算法最坏情况下要算多少个子问题、生成多少个结果”你就应该能答出卡特兰数并且说明这是因为输出本身是指数级的不存在更快的多项式解法。能讲清楚“复杂度被输出规模决定”这层含义往往是这道题在面试中的加分项。4. 进阶优化记忆化搜索与区间 DP4.1 重复子问题到底在哪朴素的递归其实藏了不少重复计算。以2*3-4*5为例当我们切在中间的 - 时左子问题是2*3而在2*3-4这个子问题内部它切在 - 时又会再次计算2*3。也就是说同一个子串2*3被不同分支反复求解。字符串越长、分支越多这种重复就越严重呈现出“子问题重叠”的典型特征——别忘了分治和动态规划之间的那道分界线就是子问题是否重叠。重叠了你就该考虑记忆化。4.2 给递归加上记忆化记忆化的做法很简单把“表达式字符串 - 结果列表”的映射缓存起来。Python 用装饰器最省事from functools import lru_cache from typing import List def diffWaysToCompute(expression: str) - List[int]: lru_cache(None) def dfs(expr: str): if expr.isdigit(): return (int(expr),) res [] for i, ch in enumerate(expr): if ch in -*: left dfs(expr[:i]) right dfs(expr[i1:]) for l in left: for r in right: if ch : res.append(l r) elif ch -: res.append(l - r) else: res.append(l * r) return tuple(res) return list(dfs(expression))两个细节一是递归函数返回 tuple 而不是 list因为 lru_cache 缓存的返回值最好不可变避免调用方误改缓存二是每个子问题都是原表达式的一个连续子串而字符串的连续子串总数只有 O(L^2) 个所以记忆化之后需要真正递归求解的不同子问题就被限制在了 O(L^2) 的数量级。有人可能会问这真的能省时间吗字符串短的时候朴素递归本来也很快省不省区别不大但一旦输入更长比如你扩展测试到 15 个以上运算符重复子问题会指数级膨胀记忆化的收益就非常明显。作为练习建议两种都写一遍亲自感受下运行时间的差异。4.3 改成区间 DP 的完整解法除了记忆化递归这道题还有一种更“工程化”的写法先把表达式解析成数字数组和运算符数组然后做区间 DP。区间 DP 的好处是没有任何递归开销也不会有字符串切片带来的拷贝代码逻辑也更容易在纸上推演。def diffWaysToCompute(expression: str) - List[int]: # 1. 解析把数字和运算符拆到两个数组 nums, ops [], [] i 0 while i len(expression): if expression[i].isdigit(): j i while j len(expression) and expression[j].isdigit(): j 1 nums.append(int(expression[i:j])) i j else: ops.append(expression[i]) i 1 # 2. dp[i][j]nums[i..j] 这组数能产生的所有结果 n len(nums) dp [[[] for _ in range(n)] for _ in range(n)] for i in range(n): dp[i][i] [nums[i]] # 3. 按区间长度从小到大递推 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 for k in range(i, j): # ops[k] 连接 nums[k] 和 nums[k1] for a in dp[i][k]: for b in dp[k 1][j]: if ops[k] : dp[i][j].append(a b) elif ops[k] -: dp[i][j].append(a - b) else: dp[i][j].append(a * b) return dp[0][n - 1]这里的思路是dp[i][j]只和两个更短的区间dp[i][k]、dp[k1][j]有关所以按区间长度从小到大递推天然保证依赖的区间都已算好。最内层仍然是两两组合结果数量和卡特兰数的关系没有变但每个区间只会被算一次不会出现字符串版里那种反复切分、反复求解同名子串的情况。对这道题的输入规模来说三种写法都能过但我个人更推荐先用递归把思路想清楚再在需要时用记忆化或 DP 收尾——先保证思路对再谈优化。5. 踩坑实录常见问题与排查速查这一节把我在实际练习和给其他人讲这道题时遇到的高频问题整理成一张速查表供你直接对照。5.1 六个高频问题的排查思路现象原因处理方式返回结果是空列表没有处理“单数字”边界。比如输入 123扫描不到运算符循环体从未执行res 一直是空在 Python 里开头加isdigit()判断在 Java 里用res.isEmpty()兜底添加解析后的数字多位数算错或丢失字符串切片或解析时把 12 拆成了 1 和 2确保只在运算符位置切片解析时连续读数字字符直到遇到运算符提交后提示结果数量不对给结果做了去重或排序去重牢记题目要求“返回所有结果”重复值必须保留不同括号结构算出相同数值是正常的输出顺序不稳定递归遍历顺序导致的结果顺序和平台预期不一致LeetCode 允许任意顺序返回不用管本地核对时可对结果排序后再比较把 - 当成负号处理看到一些负数中间结果就误以为输入也有负号导致解析逻辑错乱本题输入只含数字和二元运算符- 只表示减法不存在一元负号担心 int 溢出中间结果相乘可能会很大题目约束下 int 足够若扩展测试请换 long这五个问题里我最想再强调一下“去重”这个坑。它是典型的“理解了题目字面意思但没理解判题逻辑”的案例。很多人包括当年的我看到输出里有重复值是先愣一下然后条件反射地去重。实际上判题逻辑是把你返回的整个列表和期望列表比较顺序无所谓但每个元素的出现次数要一致。你一旦去重2*3-4*5的 -10 就只能返回一个列表长度就从 5 变成 4直接被判错。所以做题之前把题目里的 every possible result 读透比急着写代码更重要。5.2 同类题目怎么迁移分治和区间枚举这一套思想在好几类题里都能复用比如计算“不同的二叉搜索树”的数量它的递归式和卡特兰数同构、“戳气球”这类区间 DP 题、以及“为表达式添加括号求不同结果”的各种变体。它们的共同套路都是找一个切分点让左右两边变成独立子问题然后用子问题结果的组合来构造当前结果。你只要把这道题的递归模板吃透遇到这类题时第一反应就应该是“能不能切一刀”而不是去硬凑状态转移。这个思维切换是分治题从“会做一道”到“会做一类”的关键。最后分享一个我个人的做题习惯拿到这种递归题先不要开编辑器而是拿笔在纸上画递归树把最小例子比如2-1-1的完整展开画一遍。画完你自然就清楚边界在哪里、结果从哪里来、哪些子问题重复了。画明白之后代码基本就是一次写对连调试都省了。这一步花的时间远少于你写错代码后去 debug 的时间。