拆分成斐波那契序列如何用回溯？为什么要做 32 位整数剪枝？

简化版

把字符串拆成斐波那契序列，可以用回溯枚举切分。

前两个数可以自由选择；从第三个数开始，当前数必须等于前两个数之和。

如果数字有前导零、超过 32 位整数范围，或者已经大于期望和，就可以剪枝。

详细版

递归状态是当前位置 index 和当前序列 path。

每次从 index 开始尝试切出一个数字 cur。如果路径长度小于 2，可以尝试加入；否则计算 need = path[-1] + path[-2]，当前数字必须等于 need。

题目通常要求每个数在 32 位有符号整数范围内，即不超过 2^31 - 1。

当 index 到末尾且路径长度至少为 3，返回这条序列。

完整版教学

一、这题和累加数有什么关系

拆分斐波那契序列和累加数非常像，都要求从第三个数开始等于前两个数之和。区别是这题要返回具体序列，并且常见题目要求每个数字不超过 2^31 - 1。所以它既是字符串切分问题，也是带数值范围的回溯问题。

记忆钩子：斐波那契拆分 = 累加数验证 + 返回路径 + 32 位范围。

二、前两个数为什么决定后面

一旦前两个数确定，第三个数必须是它们的和，第四个数也被继续确定。因此搜索自由度主要集中在前两个切分长度。后续每一步只是在验证字符串接下来是否匹配期望值。

阶段	选择空间
第 1 个数	多种切法
第 2 个数	多种切法
第 3 个数以后	必须等于前两数之和

这就是剪枝强的原因。

三、前导零和整数范围

如果片段以 0 开头，长度大于 1，就非法。例如 "01" 不能当成 1。另外每个数不能超过 2147483647。当当前数字已经超过上限，就可以停止当前层枚举，因为继续延长只会更大。

MAX = 2^31 - 1 = 2147483647
cur > MAX -> break

这类剪枝能避免无意义的大数分支。

四、代码模板

实现如下：

function splitIntoFibonacci(num) {
  const path = []
  const MAX = 2147483647

  function dfs(index) {
    if (index === num.length) return path.length >= 3
    let cur = 0
    for (let end = index; end < num.length; end++) {
      if (num[index] === '0' && end > index) break
      cur = cur * 10 + Number(num[end])
      if (cur > MAX) break
      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) ? path : []
}

这里直接用增量构造 cur，避免频繁 slice 再转数字。

五、带数字推演

字符串 "123456579" 可以拆成：

123, 456, 579

因为 123 + 456 = 579。如果前两个切成 1,2，第三个需要 3，后续需要 5，但字符串后面是 4，这个分支会失败。

六、常见误区与追问

误区：找到前 3 个满足就结束。 必须覆盖完整字符串。
误区：忽略 32 位上限。 超范围数字不符合题目要求。
误区：允许前导零。 "01" 这种片段非法，只能单独使用 "0"。
追问：为什么 cur > need 可以 break？ 继续加位只会让 cur 更大，不可能再匹配 need。
追问：如果有多个答案怎么办？ 常见题返回任意一个合法序列即可，找到后可以立刻返回。

这些点考的是回溯剪枝的边界。

七、加强记忆

拆分斐波那契记成“先猜两段，后面按和验证”。每段要过前导零和 32 位上限；从第三段开始，当前值小于期望就继续加位，大于期望就停止当前分支，等于才递归。走完整个字符串且长度至少 3，才返回路径。

简化版

详细版