0842. 将数组拆分成斐波那契序列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 回溯

1. 📝 题目描述

• leetcode

给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。

形式上，斐波那契式 序列是一个非负整数列表 f，且满足：

• 0 <= f[i] < 2^31，（也就是说，每个整数都符合 32 位 有符号整数类型）
• f.length >= 3
• 对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。

---

示例 1：

输入：num = "1101111"
输出：[11,0,11,11]
解释：输出 [110,1,111] 也可以。

示例 2：

输入: num = "112358130"
输出: []
解释: 无法拆分。

示例 3：

输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。

---

提示：

• 1 <= num.length <= 200
• num 中只含有数字

2. 🎯 s.1 - 回溯

c

int result[200];
int resultLen;

bool bt(char* num, int idx, int n) {
    if (idx == n) return resultLen >= 3;
    long long val = 0;
    for (int i = idx; i < n; i++) {
        val = val * 10 + (num[i] - '0');
        if (val > 2147483647) break;
        if (num[idx] == '0' && i > idx) break;
        if (resultLen >= 2) {
            long long sum = (long long)result[resultLen-1] + result[resultLen-2];
            if (val < sum) continue;
            if (val > sum) break;
        }
        result[resultLen++] = (int)val;
        if (bt(num, i + 1, n)) return true;
        resultLen--;
    }
    return false;
}

int* splitIntoFibonacci(char* num, int* returnSize) {
    resultLen = 0;
    if (bt(num, 0, strlen(num))) {
        *returnSize = resultLen;
        int* res = (int*)malloc(sizeof(int) * resultLen);
        memcpy(res, result, sizeof(int) * resultLen);
        return res;
    }
    *returnSize = 0;
    return NULL;
}

js

/**
 * @param {string} num
 * @return {number[]}
 */
var splitIntoFibonacci = function (num) {
  const res = []
  const bt = (idx) => {
    if (idx === num.length) return res.length >= 3
    let val = 0
    for (let i = idx; i < num.length; i++) {
      val = val * 10 + (num.charCodeAt(i) - 48)
      if (val > 2147483647) break
      if (num[idx] === '0' && i > idx) break
      if (res.length >= 2) {
        const sum = res[res.length - 1] + res[res.length - 2]
        if (val < sum) continue
        if (val > sum) break
      }
      res.push(val)
      if (bt(i + 1)) return true
      res.pop()
    }
    return false
  }
  bt(0)
  return res
}

py

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        res = []
        def bt(idx: int) -> bool:
            if idx == len(num): return len(res) >= 3
            val = 0
            for i in range(idx, len(num)):
                val = val * 10 + int(num[i])
                if val > 2**31 - 1: break
                if num[idx] == '0' and i > idx: break
                if len(res) >= 2:
                    s = res[-1] + res[-2]
                    if val < s: continue
                    if val > s: break
                res.append(val)
                if bt(i + 1): return True
                res.pop()
            return False
        bt(0)
        return res

• 时间复杂度：$O(n^2)$，其中 n 是字符串长度
• 空间复杂度：$O(n)$

算法思路：

• 回溯枚举每个数字的切割位置，利用斐波那契性质剪枝
• 当当前值 < 前两数之和时继续拓展，> 时直接回溯