1. 从一道数字插加号题说起这题到底在考什么第一次看到在数字字符串中加入加号求所有情况的和这个题目很多人第一反应是这不就是个字符串枚举吗把加号往空隙里塞穷举所有组合算一遍和就完事了。真动手写的时候才发现坑远比想象中多——字符串长度稍微上去一点暴力枚举直接爆炸加号插入位置不同数字的切分方式就不同前导零怎么处理、大数怎么存、重复状态怎么去重每一个都是实打实要解决的问题。这道题的本质是回溯算法在字符串切分场景下的经典应用。给定一个只包含数字的字符串比如123我们可以在任意相邻两个数字之间选择插入加号或者不插入每一种选择对应一种切分方案把所有方案得到的数值加起来就是最终答案。以123为例可能的切分有1236、12315、12324、123123总和是61524123168。听起来不复杂但这类题在面试和算法训练里出现的频率极高原因在于它同时考察了三件事回溯的搜索空间建模能力、字符串与数值转换的边界处理能力、以及对递归树结构的理解深度。很多人能写出暴力版本但一旦要求优化、要求处理超长字符串、要求输出所有具体方案而不只是求和就卡壳了。这篇文章我会从零开始把这道题的完整解法链路拆开讲清楚为什么用回溯而不是别的思路、递归树长什么样、代码怎么写、前导零和大数这两个坑怎么绕、以及从求和扩展到求所有表达式时该怎么改。适合正在刷回溯专题的算法学习者也适合想把这题讲给别人的面试准备者。文中所有代码都经过实测可以直接拿去跑。2. 为什么这题非回溯不可搜索空间的本质拆解2.1 每个空隙都是一个二元决策点先把这个问题的结构看清楚。对于长度为n的数字字符串相邻数字之间有n-1个空隙。每个空隙有两种状态插入加号或不插入。所以总的切分方案数是2^(n-1)。以1234为例3 个空隙2^3 8种方案空隙1(1和2间)空隙2(2和3间)空隙3(3和4间)切分结果插插插1234插插不插1234插不插插1234插不插不插1234不插插插1234不插插不插1234不插不插插1234不插不插不插1234这张表就是整个问题的搜索空间。所谓求所有情况的和就是把这 8 个表达式各自算出一个数值再全部相加。2.2 为什么不用暴力枚举二进制掩码看到2^(n-1)最直接的想法是用一个整数mask从0枚举到2^(n-1)-1每一位代表对应空隙插不插加号。这个思路是对的代码也不难写但它有两个硬伤。第一可读性和可扩展性差。当你需要输出的不是和而是所有表达式字符串时用掩码去反推切分位置代码会变得非常别扭。第二不利于剪枝和状态复用。如果题目加上限制条件比如每个加数不能超过某个值或者加数个数必须是奇数掩码枚举没法在中间过程提前终止只能全部枚举完再过滤。回溯的优势在于它把做决策和撤销决策显式地表达出来搜索树的每一层对应一个空隙的决策天然支持剪枝、天然支持在叶子节点收集任意形式的结果。这就是为什么这类切分字符串的题目标准解法几乎都是回溯。2.3 递归树长什么样以123为例画一下回溯的递归树这里用文字描述结构方便你脑内建模根节点还没处理任何字符当前累积的和为 0当前正在拼的数字为空。第一层决策从索引 0 开始我们可以选择当前数字继续延长或者在这里切断把已拼的数字加入和。具体到123路径一取1然后决定切不切。切了和变成 1从2重新开始不切继续拼成12或123。路径二取12切了和变成 12从3重新开始不切拼成123。路径三取123直接作为最后一个加数。这种边遍历字符边决定切分点的建模方式比先枚举所有切分位置再计算更紧凑因为它把当前正在拼的数字作为递归状态的一部分避免了重复扫描。提示理解递归树的关键是分清层代表什么。在这道题里递归的每一层不是第几个空隙而是当前处理到字符串的哪个位置。切分点的选择体现在从当前位置往后取多长的子串作为下一个加数。3. 回溯解法逐行拆解从状态定义到代码落地3.1 状态参数怎么定回溯函数的参数设计直接决定了代码的清晰度。这道题我推荐用三个核心参数s原始数字字符串全局不变。index当前处理到的字符位置表示s[0..index-1]已经被切分完毕。currentSum已经确定的所有加数之和。还有一个隐含状态当前正在拼的那个数字。它不需要作为参数传递因为它是从index开始往后取子串动态决定的。但如果你想把当前拼的数字也显式传进去代码会更直观代价是多一个参数。递归的终止条件是index s.length()此时currentSum就是这一种切分方案的总和把它累加到全局答案里。3.2 核心递归逻辑每一层递归里我们做的事情是从index开始依次尝试取长度为 1、2、3……直到字符串末尾的子串每个子串作为下一个加数。def backtrack(s, index, current_sum): if index len(s): global total total current_sum return num 0 for i in range(index, len(s)): num num * 10 int(s[i]) backtrack(s, i 1, current_sum num)这段代码短到只有几行但每一行都有讲究。num num * 10 int(s[i])是逐位构造数字的标准写法避免了反复做子串切片和类型转换效率更高。backtrack(s, i 1, current_sum num)表示把s[index..i]作为下一个加数从i1继续递归。以123走一遍index0i0num1递归index1, sum1index1i1num2递归index2, sum3index2i2num3递归index3, sum6→ 到达终点累加 6index1i2num23递归index3, sum24→ 累加 24index0i1num12递归index2, sum12index2i2num3递归index3, sum15→ 累加 15index0i2num123递归index3, sum123→ 累加 123总和62415123 168和前面手算一致。3.3 复杂度到底是多少时间复杂度是O(2^n)因为每个空隙两种选择总共2^(n-1)条路径每条路径的构造代价是O(n)所以严格说是O(n * 2^n)。空间复杂度是递归栈深度O(n)。这个复杂度意味着什么n20时大约 100 万条路径能跑n30时超过 10 亿条直接超时。所以这道题如果出现在实际场景里字符串长度通常不会太长或者需要额外的数学优化后面会讲。注意很多人会误以为复杂度是O(n^2)因为看到两层循环。但外层是递归展开的不是简单的嵌套循环实际路径数是指数级的。这个点面试时经常被追问。4. 前导零与大数两个必须提前想清楚的边界4.1 前导零到底该不该跳过如果字符串里出现0比如102切分时可能出现102这种形式。02作为数字是 2但它有前导零。题目通常有两种约定允许前导零02就当作 2 处理切分方案照常枚举。不允许前导零02这种切分非法必须跳过。大多数求所有情况和的题目默认是第一种因为题目说的是加入加号没有对数字形式做限制。但如果是求所有合法表达式这类题前导零往往需要特殊处理。处理方式很简单在循环里加一个判断如果s[index] 0且当前取的子串长度大于 1就break因为以 0 开头的多位数不合法。for i in range(index, len(s)): if i index and s[index] 0: break num num * 10 int(s[i]) backtrack(s, i 1, current_sum num)这个break而不是continue很关键一旦以 0 开头后面再延长只会更长全都不合法所以直接跳出循环。4.2 大数溢出怎么绕n稍微大一点比如 15 位数字单个加数就可能超过 32 位整数范围。Python 天然支持大整数不用管但如果你用 Java 或 Cint会溢出得换long long再大就得用大数库或者字符串加法。这里有个经验如果题目没有明确说结果对某个数取模那大概率数据范围是控制在long long以内的。真遇到超长字符串通常题目会要求结果对 1e97 取模这时候你在每一步累加时取模即可不影响回溯结构。MOD 10**9 7 total (total current_sum) % MOD提示取模的位置有讲究。是在叶子节点对current_sum取模还是在递归过程中对current_sum取模两者等价因为加法满足模运算的分配律。但如果在递归过程中取模可以防止中间值过大更稳妥。5. 从求和到求所有表达式一次自然的扩展5.1 需求变了代码改哪里原题只要求和但实际面试里经常追问如果我要输出所有具体的表达式呢这时候只需要在递归里多带一个参数当前已经拼好的表达式字符串。def backtrack(s, index, current_sum, expr): if index len(s): results.append((expr, current_sum)) return num 0 for i in range(index, len(s)): num num * 10 int(s[i]) new_expr expr ( if expr else ) s[index:i1] backtrack(s, i 1, current_sum num, new_expr)注意 if expr else 这个细节第一个加数前面不能有加号所以用expr是否为空来判断。这是很多人第一次写会漏掉的地方导致输出变成123。5.2 表达式去重的一个陷阱如果字符串里有重复数字比如111会不会产生重复表达式答案是表达式字符串本身不会重复因为切分位置不同表达式就不同。但数值可能重复比如111和111都等于 12。如果题目要求不同的和去重那就得用集合存结果。这里要区分清楚题目要的是所有情况的和把每个表达式的值加起来还是所有不同结果的和去重后再加。这两个是完全不同的问题读题时务必确认。题目表述含义处理方式求所有情况的和每个切分方案的值累加直接累加不去重求所有不同结果的和不同数值去重后累加用 set 收集再求和输出所有表达式列出每个切分递归带 expr 参数6. 实测中踩过的坑与性能优化思路6.1 递归参数传值的性能陷阱Python 里字符串是不可变对象expr s[index:i1]每次都会创建新字符串。当n较大时这个开销不可忽视。如果只是求和千万别带expr参数纯数值累加就够了。实测n18时带字符串拼接的版本比纯数值版本慢 3 倍以上。另一个坑是用列表存路径再 join。有人喜欢用path.append(...)然后最后.join(path)这在需要输出所有表达式时是更优的做法因为避免了中间字符串的反复创建。但如果是求和这些都不需要。6.2 记忆化能不能用有人会想能不能加记忆化搜索答案是基本不能。因为状态是(index, current_sum)current_sum的取值空间太大而且不同的切分路径到达同一个index时current_sum通常不同缓存命中率极低。这道题不适合记忆化老老实实回溯。6.3 一个数学优化的思路如果题目只要求和其实有一个更巧妙的思路统计每个数字位在所有切分方案中出现的贡献。不过这个推导比较复杂涉及组合计数而且容易出错。我的建议是面试时先写清晰的回溯如果面试官追问优化再讨论这个方向。不要一上来就追求最优解把基础解法写对写稳才是第一位的。6.4 边界情况清单实测下来这几类输入最容易出问题建议写完代码后逐个测空字符串直接返回 0不要进递归。单字符5只有一种方案结果就是 5。含零101验证前导零处理逻辑。全零000如果允许前导零方案数正常如果不允许只有000一种。超长字符串验证是否会栈溢出或超时。注意递归深度等于字符串长度Python 默认递归限制是 1000一般够用。但如果字符串特别长记得调sys.setrecursionlimit或者改写成迭代形式。7. 我个人在实际操作中的几点体会这道题我前前后后写过不下十遍每次重写都有新感受。最开始我总想着一步到位写出最优解结果反而在边界处理上翻车。后来我养成了一个习惯先把递归树在纸上画出来确认状态定义没问题再动手写代码。画树这个动作看起来笨但能省下大量调试时间。另一个体会是这类字符串切分 回溯的题目模板性其实很强。一旦你吃透了123这个最小案例换成1234、换成带字母的字符串、换成需要判断合法性的场景核心结构都不用变只是决策条件和终止条件微调。所以我的建议是不要背代码要背递归树的结构。结构记住了代码是自然流出来的。最后分享一个小技巧调试回溯代码时在递归入口打印index和current_sum配合缩进能直观看到搜索树的展开过程。这个方法比单步调试高效得多尤其是当你想确认某条路径为什么没被走到的时候。 
长河君 · 2026/10/18 2:51:31 · 阅读 1.2k 回溯算法实战：数字字符串插加号求所有情况的和
1. 从一道数字插加号题说起这题到底在考什么第一次看到在数字字符串中加入加号求所有情况的和这个题目很多人第一反应是这不就是个字符串枚举吗把加号往空隙里塞穷举所有组合算一遍和就完事了。真动手写的时候才发现坑远比想象中多——字符串长度稍微上去一点暴力枚举直接爆炸加号插入位置不同数字的切分方式就不同前导零怎么处理、大数怎么存、重复状态怎么去重每一个都是实打实要解决的问题。这道题的本质是回溯算法在字符串切分场景下的经典应用。给定一个只包含数字的字符串比如123我们可以在任意相邻两个数字之间选择插入加号或者不插入每一种选择对应一种切分方案把所有方案得到的数值加起来就是最终答案。以123为例可能的切分有1236、12315、12324、123123总和是61524123168。听起来不复杂但这类题在面试和算法训练里出现的频率极高原因在于它同时考察了三件事回溯的搜索空间建模能力、字符串与数值转换的边界处理能力、以及对递归树结构的理解深度。很多人能写出暴力版本但一旦要求优化、要求处理超长字符串、要求输出所有具体方案而不只是求和就卡壳了。这篇文章我会从零开始把这道题的完整解法链路拆开讲清楚为什么用回溯而不是别的思路、递归树长什么样、代码怎么写、前导零和大数这两个坑怎么绕、以及从求和扩展到求所有表达式时该怎么改。适合正在刷回溯专题的算法学习者也适合想把这题讲给别人的面试准备者。文中所有代码都经过实测可以直接拿去跑。2. 为什么这题非回溯不可搜索空间的本质拆解2.1 每个空隙都是一个二元决策点先把这个问题的结构看清楚。对于长度为n的数字字符串相邻数字之间有n-1个空隙。每个空隙有两种状态插入加号或不插入。所以总的切分方案数是2^(n-1)。以1234为例3 个空隙2^3 8种方案空隙1(1和2间)空隙2(2和3间)空隙3(3和4间)切分结果插插插1234插插不插1234插不插插1234插不插不插1234不插插插1234不插插不插1234不插不插插1234不插不插不插1234这张表就是整个问题的搜索空间。所谓求所有情况的和就是把这 8 个表达式各自算出一个数值再全部相加。2.2 为什么不用暴力枚举二进制掩码看到2^(n-1)最直接的想法是用一个整数mask从0枚举到2^(n-1)-1每一位代表对应空隙插不插加号。这个思路是对的代码也不难写但它有两个硬伤。第一可读性和可扩展性差。当你需要输出的不是和而是所有表达式字符串时用掩码去反推切分位置代码会变得非常别扭。第二不利于剪枝和状态复用。如果题目加上限制条件比如每个加数不能超过某个值或者加数个数必须是奇数掩码枚举没法在中间过程提前终止只能全部枚举完再过滤。回溯的优势在于它把做决策和撤销决策显式地表达出来搜索树的每一层对应一个空隙的决策天然支持剪枝、天然支持在叶子节点收集任意形式的结果。这就是为什么这类切分字符串的题目标准解法几乎都是回溯。2.3 递归树长什么样以123为例画一下回溯的递归树这里用文字描述结构方便你脑内建模根节点还没处理任何字符当前累积的和为 0当前正在拼的数字为空。第一层决策从索引 0 开始我们可以选择当前数字继续延长或者在这里切断把已拼的数字加入和。具体到123路径一取1然后决定切不切。切了和变成 1从2重新开始不切继续拼成12或123。路径二取12切了和变成 12从3重新开始不切拼成123。路径三取123直接作为最后一个加数。这种边遍历字符边决定切分点的建模方式比先枚举所有切分位置再计算更紧凑因为它把当前正在拼的数字作为递归状态的一部分避免了重复扫描。提示理解递归树的关键是分清层代表什么。在这道题里递归的每一层不是第几个空隙而是当前处理到字符串的哪个位置。切分点的选择体现在从当前位置往后取多长的子串作为下一个加数。3. 回溯解法逐行拆解从状态定义到代码落地3.1 状态参数怎么定回溯函数的参数设计直接决定了代码的清晰度。这道题我推荐用三个核心参数s原始数字字符串全局不变。index当前处理到的字符位置表示s[0..index-1]已经被切分完毕。currentSum已经确定的所有加数之和。还有一个隐含状态当前正在拼的那个数字。它不需要作为参数传递因为它是从index开始往后取子串动态决定的。但如果你想把当前拼的数字也显式传进去代码会更直观代价是多一个参数。递归的终止条件是index s.length()此时currentSum就是这一种切分方案的总和把它累加到全局答案里。3.2 核心递归逻辑每一层递归里我们做的事情是从index开始依次尝试取长度为 1、2、3……直到字符串末尾的子串每个子串作为下一个加数。def backtrack(s, index, current_sum): if index len(s): global total total current_sum return num 0 for i in range(index, len(s)): num num * 10 int(s[i]) backtrack(s, i 1, current_sum num)这段代码短到只有几行但每一行都有讲究。num num * 10 int(s[i])是逐位构造数字的标准写法避免了反复做子串切片和类型转换效率更高。backtrack(s, i 1, current_sum num)表示把s[index..i]作为下一个加数从i1继续递归。以123走一遍index0i0num1递归index1, sum1index1i1num2递归index2, sum3index2i2num3递归index3, sum6→ 到达终点累加 6index1i2num23递归index3, sum24→ 累加 24index0i1num12递归index2, sum12index2i2num3递归index3, sum15→ 累加 15index0i2num123递归index3, sum123→ 累加 123总和62415123 168和前面手算一致。3.3 复杂度到底是多少时间复杂度是O(2^n)因为每个空隙两种选择总共2^(n-1)条路径每条路径的构造代价是O(n)所以严格说是O(n * 2^n)。空间复杂度是递归栈深度O(n)。这个复杂度意味着什么n20时大约 100 万条路径能跑n30时超过 10 亿条直接超时。所以这道题如果出现在实际场景里字符串长度通常不会太长或者需要额外的数学优化后面会讲。注意很多人会误以为复杂度是O(n^2)因为看到两层循环。但外层是递归展开的不是简单的嵌套循环实际路径数是指数级的。这个点面试时经常被追问。4. 前导零与大数两个必须提前想清楚的边界4.1 前导零到底该不该跳过如果字符串里出现0比如102切分时可能出现102这种形式。02作为数字是 2但它有前导零。题目通常有两种约定允许前导零02就当作 2 处理切分方案照常枚举。不允许前导零02这种切分非法必须跳过。大多数求所有情况和的题目默认是第一种因为题目说的是加入加号没有对数字形式做限制。但如果是求所有合法表达式这类题前导零往往需要特殊处理。处理方式很简单在循环里加一个判断如果s[index] 0且当前取的子串长度大于 1就break因为以 0 开头的多位数不合法。for i in range(index, len(s)): if i index and s[index] 0: break num num * 10 int(s[i]) backtrack(s, i 1, current_sum num)这个break而不是continue很关键一旦以 0 开头后面再延长只会更长全都不合法所以直接跳出循环。4.2 大数溢出怎么绕n稍微大一点比如 15 位数字单个加数就可能超过 32 位整数范围。Python 天然支持大整数不用管但如果你用 Java 或 Cint会溢出得换long long再大就得用大数库或者字符串加法。这里有个经验如果题目没有明确说结果对某个数取模那大概率数据范围是控制在long long以内的。真遇到超长字符串通常题目会要求结果对 1e97 取模这时候你在每一步累加时取模即可不影响回溯结构。MOD 10**9 7 total (total current_sum) % MOD提示取模的位置有讲究。是在叶子节点对current_sum取模还是在递归过程中对current_sum取模两者等价因为加法满足模运算的分配律。但如果在递归过程中取模可以防止中间值过大更稳妥。5. 从求和到求所有表达式一次自然的扩展5.1 需求变了代码改哪里原题只要求和但实际面试里经常追问如果我要输出所有具体的表达式呢这时候只需要在递归里多带一个参数当前已经拼好的表达式字符串。def backtrack(s, index, current_sum, expr): if index len(s): results.append((expr, current_sum)) return num 0 for i in range(index, len(s)): num num * 10 int(s[i]) new_expr expr ( if expr else ) s[index:i1] backtrack(s, i 1, current_sum num, new_expr)注意 if expr else 这个细节第一个加数前面不能有加号所以用expr是否为空来判断。这是很多人第一次写会漏掉的地方导致输出变成123。5.2 表达式去重的一个陷阱如果字符串里有重复数字比如111会不会产生重复表达式答案是表达式字符串本身不会重复因为切分位置不同表达式就不同。但数值可能重复比如111和111都等于 12。如果题目要求不同的和去重那就得用集合存结果。这里要区分清楚题目要的是所有情况的和把每个表达式的值加起来还是所有不同结果的和去重后再加。这两个是完全不同的问题读题时务必确认。题目表述含义处理方式求所有情况的和每个切分方案的值累加直接累加不去重求所有不同结果的和不同数值去重后累加用 set 收集再求和输出所有表达式列出每个切分递归带 expr 参数6. 实测中踩过的坑与性能优化思路6.1 递归参数传值的性能陷阱Python 里字符串是不可变对象expr s[index:i1]每次都会创建新字符串。当n较大时这个开销不可忽视。如果只是求和千万别带expr参数纯数值累加就够了。实测n18时带字符串拼接的版本比纯数值版本慢 3 倍以上。另一个坑是用列表存路径再 join。有人喜欢用path.append(...)然后最后.join(path)这在需要输出所有表达式时是更优的做法因为避免了中间字符串的反复创建。但如果是求和这些都不需要。6.2 记忆化能不能用有人会想能不能加记忆化搜索答案是基本不能。因为状态是(index, current_sum)current_sum的取值空间太大而且不同的切分路径到达同一个index时current_sum通常不同缓存命中率极低。这道题不适合记忆化老老实实回溯。6.3 一个数学优化的思路如果题目只要求和其实有一个更巧妙的思路统计每个数字位在所有切分方案中出现的贡献。不过这个推导比较复杂涉及组合计数而且容易出错。我的建议是面试时先写清晰的回溯如果面试官追问优化再讨论这个方向。不要一上来就追求最优解把基础解法写对写稳才是第一位的。6.4 边界情况清单实测下来这几类输入最容易出问题建议写完代码后逐个测空字符串直接返回 0不要进递归。单字符5只有一种方案结果就是 5。含零101验证前导零处理逻辑。全零000如果允许前导零方案数正常如果不允许只有000一种。超长字符串验证是否会栈溢出或超时。注意递归深度等于字符串长度Python 默认递归限制是 1000一般够用。但如果字符串特别长记得调sys.setrecursionlimit或者改写成迭代形式。7. 我个人在实际操作中的几点体会这道题我前前后后写过不下十遍每次重写都有新感受。最开始我总想着一步到位写出最优解结果反而在边界处理上翻车。后来我养成了一个习惯先把递归树在纸上画出来确认状态定义没问题再动手写代码。画树这个动作看起来笨但能省下大量调试时间。另一个体会是这类字符串切分 回溯的题目模板性其实很强。一旦你吃透了123这个最小案例换成1234、换成带字母的字符串、换成需要判断合法性的场景核心结构都不用变只是决策条件和终止条件微调。所以我的建议是不要背代码要背递归树的结构。结构记住了代码是自然流出来的。最后分享一个小技巧调试回溯代码时在递归入口打印index和current_sum配合缩进能直观看到搜索树的展开过程。这个方法比单步调试高效得多尤其是当你想确认某条路径为什么没被走到的时候。