累加数如何用回溯验证？前导零和大整数怎么处理？

简化版

累加数要求字符串能拆成至少 3 个数，并且从第三个数开始，每个数等于前两个数之和。

回溯时依次切出数字，路径里已有至少两个数时，新数字必须等于前两个数之和。

如果某段数字以 0 开头且长度大于 1，要直接跳过。

详细版

递归状态是当前切分下标 index 和已经切出的数字路径 path。

从 index 开始尝试不同长度的数字片段。每个片段要检查：

前导零是否合法；
如果已有两个数字，当前数字是否等于前两个之和；
如果当前数字已经大于期望和，可以提前停止。

JavaScript 中数字可能超过安全整数，稳妥写法可以用 BigInt。

当走到字符串末尾且路径长度至少为 3，说明是累加数。

完整版教学

一、累加数的结构是什么

累加数像字符串版斐波那契：前两个数自由选择，后面的数被前两个数唯一决定。比如 "112358" 可以拆成 1,1,2,3,5,8。这类题的搜索重点在前两个数怎么切，以及后续是否严格匹配。

记忆钩子：累加数只有前两个数有自由度，后面都被和约束住。

二、回溯如何切字符串

从当前位置 index 出发，枚举结束位置 end，得到片段 s[index..end]。把片段转成数字后，判断它能否加入当前路径。如果可以，就递归处理后面的字符串。

路径长度	当前片段要求
0	任意合法数字
1	任意合法数字
>=2	必须等于前两个数之和

这个约束让搜索树很快收缩。

三、前导零为什么要剪掉

数字不能有前导零，除非它本身就是 "0"。例如 "01" 不能当成数字 1。否则同一个数字会有多种字符串表示，题目语义也会混乱。

"0" 合法
"01" 不合法
"001" 不合法

所以一旦 s[index] === '0'，当前层只能尝试长度为 1 的片段。

四、代码模板

实现如下：

function isAdditiveNumber(num) {
  const path = []

  function dfs(index) {
    if (index === num.length) return path.length >= 3
    for (let end = index; end < num.length; end++) {
      if (num[index] === '0' && end > index) break
      const cur = BigInt(num.slice(index, end + 1))
      const len = path.length
      if (len >= 2) {
        const need = path[len - 1] + path[len - 2]
        if (cur < need) continue
        if (cur > need) break
      }
      path.push(cur)
      if (dfs(end + 1)) return true
      path.pop()
    }
    return false
  }

  return dfs(0)
}

用 BigInt 可以避免超出 Number 安全整数范围。

五、带数字推演

字符串 "112358"：

先切 1, 1
下一个必须是 2，匹配
下一个必须是 3，匹配
下一个必须是 5，匹配
下一个必须是 8，匹配
到末尾且长度 >= 3，返回 true

如果切成 11,2，下一个必须是 13，但后面开头是 3，会失败。

六、常见误区与追问

误区：允许 01 这种数字片段。 前导零会产生非法切分。
误区：只要出现三个数满足一次相加就返回 true。 必须整个字符串都能按规则切完。
误区：用 Number 处理特别长字符串。 可能超过安全整数，比较结果不可靠。
追问：为什么 cur > need 可以 break？ 当前片段继续变长只会更大，不可能重新等于 need。
追问：复杂度高吗？ 前两个数有多种切法，但后续被和约束，实际剪枝较强。

这些问题考的是字符串切分和数值约束。

七、加强记忆

累加数记成“前两个随便切，后面必须等于和”。每段先过前导零检查；路径长度达到 2 后，当前数只能匹配前两个数之和。用 BigInt 防止大整数失真。走到末尾且至少 3 个数，才算验证成功。

简化版

详细版