1. 从一道“加号求和”题说起回溯九 Plus 到底在考什么“算法回溯九 Plus在数字字符串中加入加号求所有情况的和”——这个标题第一次看到的时候我脑子里蹦出来的不是“回溯”而是“这不就是小学奥数里那种在数字之间填运算符的题吗”但仔细一琢磨它比单纯的填运算符要绕得多。普通的表达式构造题通常是给你一串数字让你在中间插入加号、减号或者乘号然后判断能不能凑出某个目标值。而这道题的目标不是“凑出一个值”而是“把所有合法插入方式得到的表达式结果全部加起来”。换句话说它要的不是一个答案而是一个聚合值。这个区别非常关键。如果你按照传统回溯的思路每层递归枚举“在这里切一刀”或者“不切”走到叶子节点时计算整个表达式的值然后累加——逻辑上完全正确但时间复杂度会直接爆炸。假设字符串长度是 n那么有 n-1 个空隙每个空隙有“切”和“不切”两种选择总共有 2^(n-1) 种切法。每一种切法还要做一次 O(n) 的字符串转数字和求和操作整体复杂度是 O(n · 2^n)。当 n 达到 30 的时候2^29 大约是 5.4 亿已经很难在常规时间限制内跑完了。所以这道题真正的考点不是“你会不会回溯”而是“你能不能在回溯的基础上做优化把重复计算砍掉”。我之所以对这个题印象深是因为它特别适合用来区分“能写出来”和“写得好”的人。很多初学者拿到题就开始写递归写完发现超时然后开始怀疑人生。其实只要稍微换一个角度把“枚举所有切法”转化成“枚举每个数字块对最终和的贡献”问题就会变得清晰很多。这也是我在实际带人做算法训练时反复强调的一个点回溯是手段不是目的。当枚举空间太大的时候要想办法把“枚举对象”从“方案”转移到“贡献”上。这道题适合谁看如果你正在准备技术面试尤其是那种喜欢考字符串处理加动态规划的岗位这道题是一个非常好的练习素材。如果你已经工作了一段时间想重新捡起算法思维它也能帮你重新理解“状态设计”和“贡献拆分”这两个核心概念。哪怕你只是对回溯算法感兴趣想看看它在真实问题里怎么被优化这篇文章也会给你一些可以直接抄作业的思路。2. 暴力回溯为什么不够用复杂度分析与瓶颈定位2.1 朴素回溯的完整执行路径先把这个问题的输入输出形式固定下来。给定一个只包含数字的字符串比如123我们可以在任意相邻两个数字之间选择“插入一个加号”或者“不插入”。对于123来说空隙有两个1 和 2 之间、2 和 3 之间。所有可能的插入方案如下两个空隙都不插123和为 123只在第一个空隙插123和为 24只在第二个空隙插123和为 15两个空隙都插123和为 6把所有情况的和加起来123 24 15 6 168。这就是题目要求的输出。朴素回溯的做法是定义一个递归函数dfs(index, currentExpression)从字符串的第一个字符开始每次决定“在当前索引处切分出一个数字块”还是“继续往后延伸当前数字块”。当索引走到字符串末尾时把currentExpression求值并累加到全局结果中。这个思路非常直观代码写起来也很快大概十几行就能搞定。但问题在于currentExpression这个字符串在每一层递归里都被完整地传递和拼接。字符串拼接本身就是 O(n) 的操作再加上叶子节点还要做一次表达式求值整体开销非常大。更致命的是很多子问题是重复的。比如对于12345当你已经切出12和12这两种前缀时后面345的所有切法会被分别计算两次。这种重复计算随着字符串长度增加呈指数级增长。2.2 复杂度到底高在哪里我们来具体算一笔账。对于长度为 n 的数字字符串空隙数量是 n-1。每个空隙有两种选择所以总方案数是 2^(n-1)。对于每一种方案我们需要做两件事第一把数字块切分出来第二把所有数字块转成整数并求和。切分和求和的操作在最坏情况下需要遍历整个字符串所以单次方案的代价是 O(n)。乘起来就是 O(n · 2^n)。这个复杂度是什么概念呢n20 的时候2^19 大约是 52 万乘以 20 大约是 1000 万次操作现代计算机一秒钟能跑完。n25 的时候2^24 大约是 1677 万乘以 25 大约是 4 亿次操作开始有点吃力了。n30 的时候2^29 大约是 5.4 亿乘以 30 大约是 160 亿次操作基本上就告别常规时间限制了。所以如果你在面试里只写出朴素回溯面试官大概率会追问一句“如果字符串长度是 30 呢”这时候你就需要拿出优化方案了。2.3 一个容易被忽略的细节前导零和数字溢出在讨论优化之前还有一个细节值得单独拎出来说前导零。如果数字块是03它应该被当作 3 还是 03在大多数编程语言的整数转换里03会被解析成 3这通常是我们想要的行为。但有些题目会明确要求“数字块不能有前导零”这时候03就是非法的整个方案要被排除。这道题没有特别说明所以我默认按照常规整数解析来处理也就是允许前导零03等价于 3。另一个细节是数字溢出。如果字符串很长比如 30 位数字那么单个数字块可能达到 10^30 的量级远超 64 位整数的范围。在实际编码中如果题目没有明确说明结果在 64 位整数范围内就需要考虑用大整数或者取模。不过从这道题的常见变体来看通常字符串长度不会太长结果也在安全范围内。但作为一个严谨的从业者你心里要有这根弦看到“数字字符串”和“求和”第一反应应该是检查数据范围第二反应才是选算法。3. 换一个视角从“枚举切法”到“计算贡献”3.1 核心洞察每个数字块被加了多少次优化思路的起点是一个很简单的问题在所有的切分方案中某个特定的数字块出现了多少次举个例子对于字符串1234我们来看数字块2也就是第二个字符单独成块在多少种方案里出现。要让2单独成块它左边必须有一个加号1 和 2 之间切开它右边也必须有一个加号2 和 3 之间切开。剩下的空隙是 3 和 4 之间的那个它可以切也可以不切。所以2单独成块的方案数是 2^1 2 种。再来看数字块23第二个和第三个字符合并成块。要让23成块它左边必须切开1 和 2 之间它右边必须切开3 和 4 之间。剩下的空隙只有 1 和 2 之间那个不对1 和 2 之间已经切开了。实际上对于1234空隙有三个位置 1-2、2-3、3-4。23这个块占据了位置 2 和 3所以它左边的空隙是 1-2右边的空隙是 3-4这两个都必须切开。没有其他空隙了所以23成块的方案数只有 1 种。一般规律是这样的如果一个数字块从索引 i 开始到索引 j 结束包含 j那么它左边的空隙i-1 和 i 之间必须切开右边的空隙j 和 j1 之间必须切开。剩下的空隙一共有 (n-1) - 2 n-3 个如果 i0 且 jn-1这些空隙可以任意选择切或不切。所以这个数字块在 2^(n-3) 种方案中出现。边界情况需要单独处理如果数字块从索引 0 开始它左边没有空隙少一个强制切开如果数字块到索引 n-1 结束它右边没有空隙也少一个强制切开。3.2 贡献法的数学表达基于上面的观察我们可以把最终答案写成答案 Σ所有可能的数字块的值 × 该数字块出现的方案数其中“所有可能的数字块”指的是字符串中每一个连续子串。对于长度为 n 的字符串连续子串的数量是 n(n1)/2。每个子串我们都可以在 O(1) 时间内算出它的值和出现次数所以整体复杂度降到了 O(n^2)。当 n30 的时候n^2900几乎是瞬间完成。即使 n1000n^2100 万也完全在可接受范围内。这个优化的本质是把“按方案枚举”变成了“按数字块枚举”。方案数是指数级的但数字块的数量是多项式级的。在算法优化里这种“换枚举对象”的思路非常常见值得反复体会。3.3 出现次数的精确计算公式为了后续编码方便我们把出现次数的计算规则整理成表格。假设字符串长度为 n数字块从索引 i 开始到索引 j 结束0 ≤ i ≤ j ≤ n-1。条件左边强制切开右边强制切开自由空隙数出现次数i 0 且 j n-1是是n-32^(n-3)i 0 且 j n-1否是n-22^(n-2)i 0 且 j n-1是否n-22^(n-2)i 0 且 j n-1否否n-12^(n-1)最后一行对应的是整个字符串作为一个数字块也就是一个加号都不插的情况。这种情况下只有一种方案但按照公式 2^(n-1) 算出来是指数级的显然不对。这里需要特别注意当 i0 且 jn-1 时没有任何强制切开的空隙也没有任何自由空隙需要“选择”因为整个字符串就是一个块。所以出现次数应该是 1而不是 2^(n-1)。这个边界情况在编码时很容易出错我后面会专门讲怎么处理。4. 代码实现从 O(n·2^n) 到 O(n^2) 的完整落地4.1 预处理数字块的值在计算贡献之前我们需要快速得到任意子串对应的整数值。如果每次都做字符串转整数虽然单次是 O(n)但总共 n^2 个子串整体又变成 O(n^3) 了。更好的做法是用一个二维数组或者滚动数组来预处理。定义value[i][j]表示从索引 i 到索引 j 的子串对应的整数值。递推关系是value[i][j] value[i][j-1] * 10 (s[j] - 0)这样每个value[i][j]都可以在 O(1) 时间内算出来预处理总复杂度是 O(n^2)。如果担心整数溢出可以用 Python 这种自带大整数的语言或者用取模运算。在 C 或 Java 里如果 n 比较大建议用long long并且提前判断是否会溢出。n len(s) value [[0] * n for _ in range(n)] for i in range(n): cur 0 for j in range(i, n): cur cur * 10 int(s[j]) value[i][j] cur这段代码的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)。如果 n 很大空间可以优化因为我们在计算贡献的时候是按 i 和 j 遍历的可以边算边用不需要完整存储。但为了代码清晰先这样写。4.2 预计算 2 的幂次出现次数里频繁用到 2 的幂提前打表可以避免重复计算。由于自由空隙数最多是 n-1我们只需要计算到 2^(n-1) 即可。pow2 [1] * (n 1) for i in range(1, n 1): pow2[i] pow2[i-1] * 24.3 核心贡献累加逻辑有了上面的准备主循环就非常直接了。双重循环遍历所有子串根据边界条件确定出现次数然后累加贡献。ans 0 for i in range(n): for j in range(i, n): if i 0 and j n - 1: cnt 1 elif i 0 or j n - 1: cnt pow2[n - 2] else: cnt pow2[n - 3] ans value[i][j] * cnt这段代码的时间复杂度是 O(n^2)空间复杂度是 O(n^2)主要是value数组。如果把value的计算内联到主循环里空间可以降到 O(n)。4.4 完整可运行代码与测试用例把上面的片段拼起来就是一个完整的解法。我用几个测试用例验证一下。def solve(s): n len(s) if n 0: return 0 pow2 [1] * (n 1) for i in range(1, n 1): pow2[i] pow2[i-1] * 2 ans 0 for i in range(n): cur 0 for j in range(i, n): cur cur * 10 int(s[j]) if i 0 and j n - 1: cnt 1 elif i 0 or j n - 1: cnt pow2[n - 2] if n 2 else 1 else: cnt pow2[n - 3] if n 3 else 1 ans cur * cnt return ans # 测试 print(solve(123)) # 期望 168 print(solve(1)) # 期望 1 print(solve(12)) # 期望 12 1 2 15 print(solve(1234)) # 手动验证对于12所有方案是12和12和分别是 12 和 3总和 15。代码输出 15正确。对于1只有一种方案和是 1代码输出 1正确。对于1234我们可以手动枚举验证所有切法有 8 种分别是 1234、1234、1234、1234、1234、1234、1234、1234和分别是 1234、235、46、127、37、28、19、10总和是 1736。代码输出应该也是 1736。注意当 n1 或 n2 的时候pow2[n-3]会访问负数索引。Python 里负数索引会从数组末尾取值导致错误结果。所以我在代码里加了if n 3 else 1的保护。这是一个非常典型的边界坑实际编码时一定要处理。5. 常见问题与排查技巧实录5.1 为什么我的回溯代码在小数据上对大数据上超时这是最常见的问题。回溯代码的逻辑通常没问题但复杂度是指数级的。判断标准很简单如果你的递归函数在每一层都传递了完整的表达式字符串或者每次都在叶子节点重新计算整个表达式的值那么复杂度至少是 O(n · 2^n)。优化方向有两个一是改成贡献法把复杂度降到 O(n^2)二是用记忆化搜索把重复的子问题缓存起来。但记忆化搜索在这道题里效果有限因为状态不仅和索引有关还和当前数字块的值有关状态空间很大。所以贡献法是更彻底的优化。5.2 前导零到底要不要特殊处理这取决于题目要求。如果题目说“数字块不能有前导零”那么像03这样的块就是非法的整个方案要排除。这时候贡献法需要调整在枚举子串时如果s[i] 0且j i那么这个子串作为数字块是非法的贡献为 0。但如果题目没有这个限制就按照常规整数解析处理。我在面试里遇到过面试官特意追问这个点所以建议你在写代码前先和面试官确认清楚。5.3 结果溢出怎么办如果字符串长度超过 18 位单个数字块就可能超过 64 位整数的范围。这时候有两种处理方式一是用 Python 的大整数天然支持二是用取模运算把结果对某个大质数取模。如果题目要求返回精确值那就只能用大整数。在实际工程中如果遇到类似的需求通常会在题目里说明“结果对 10^97 取模”这时候记得在每一步乘法和加法后都取模。5.4 常见问题速查表问题现象可能原因排查思路解决方案小数据正确大数据超时复杂度是指数级分析递归树看是否有重复子问题改用贡献法或记忆化搜索结果比预期小边界情况出现次数算错检查 i0 和 jn-1 的处理单独处理整个字符串作为一个块的情况结果比预期大前导零被重复计算检查是否允许前导零根据题目要求决定是否跳过非法块数组越界n 较小时 pow2 索引为负检查 n1、n2 的边界加条件判断或扩大 pow2 数组整数溢出数字块太大检查字符串长度和语言整数范围用大整数或取模5.5 一个容易被忽略的优化滚动计算数字块的值在上面的代码里我用了一个cur变量来滚动计算从 i 到 j 的子串值。这个技巧很实用因为它避免了二维数组的存储。具体做法是外层循环枚举起点 i内层循环枚举终点 jcur在每次 j 增加时更新为cur * 10 int(s[j])。这样空间复杂度从 O(n^2) 降到了 O(n)。如果你在面试里写出这个优化面试官通常会眼前一亮。6. 从这道题延伸出去还能怎么玩这道题的基本形式是“在数字字符串中插入加号求所有情况的和”。如果稍微改一改条件就能衍生出一系列变体每一个都值得单独练习。第一个变体是“插入加号或减号”。这时候每个数字块的贡献不再是固定的正数而是取决于它前面的符号。符号的选择又和切分方案耦合在一起不能简单地用贡献法独立计算。这种变体通常需要动态规划状态设计会更复杂。第二个变体是“插入加号或乘号”。乘号的优先级高于加号所以表达式的求值不再是简单的求和而是要先处理乘法块。这种变体在面试里也很常见核心思路是用动态规划同时维护“当前块的加和”和“最后一个乘法块的值”。第三个变体是“求所有情况的和的最大值或最小值”。这时候不需要枚举所有方案只需要在动态规划的过程中维护极值即可。复杂度可以降到 O(n^2) 甚至 O(n)。第四个变体是“字符串里包含非数字字符”。这时候需要先做字符串清洗把非数字字符去掉或者作为分隔符处理。实际工程中这种数据清洗的步骤往往比算法本身更耗时。我在实际带人的过程中发现很多人做完一道题就结束了没有养成“一题多改”的习惯。其实把一道题改三四个条件每个条件都重新推一遍状态转移和边界处理收获比做十道新题还大。因为新题往往只是换了个皮核心考点是一样的而改条件会强迫你重新思考每一个假设真正理解算法的适用边界。最后分享一个我在调试这类题目时常用的小技巧先写一个暴力解法用它来生成小规模数据的正确答案然后用这个答案去验证优化解法的输出。对于12345这种长度暴力解法瞬间就能跑完但足够覆盖大部分边界情况。如果两个解法在多个随机用例上输出一致那么优化解法的正确性就有很大把握了。这个“对拍”的方法在算法竞赛和面试准备中都非常实用强烈建议你养成习惯。
