🥈842. 将数组拆分成斐波那契序列@

🥈Medium

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

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

• ，（也就是说，每个整数都符合 32 位有符号整数类型）
• 
• 对于所有的，都有 成立

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

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

示例 1：

输入："123456579"
输出：[123,456,579]

示例 2：

输入: "11235813"
输出: [1,1,2,3,5,8,13]

示例 3：

输入: "112358130"
输出: []
解释: 这项任务无法完成。

示例 4：

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

示例 5：

输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。

提示：

• 1 <= S.length <= 200
• 字符串 S 中只含有数字

题解

完全没有思路😭，看看官方题解吧：

回溯+剪枝

使用列表存储拆分出来的数，回溯过程中维护该列表的元素，列表初始为空。遍历字符串所有可能的前缀，作为当前被拆分的数，然后对剩下部分继续拆分，直到整个字符串拆分完毕。

根据斐波那契的通项公式，需要从第三个数开始，每个数都是前两个数的和，因此从第三个数开始，需要判定拆分出来的数是否为前两个数的和，如果不满足，则不能被拆分。

整个回溯过程中，还有三处可以进行剪枝优化：

1. 第一个拆分出的数如果不是0，且剩下的字符串以0开头，这样是没有结果的
2. 如果列表中至少有两个数，且拆分出的数已经大于最后两个数之和，就不用再继续拆分了
3. 拆分出的数必须符合 32 位有符号整数类型，即每个数必须在的范围内，如果拆分出的数大于，则不符合要求，长度更大的数的数值也一定更大，一定也大于，因此不可能继续拆分得到斐波那契式序列

当整个字符串拆分完毕，如果列表中至少有三个数，则得到一个符合要求的斐波那契序列，返回列表。如果没有找到符合要求的斐波那契序列，则返回空列表。

Python

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = list()
        def backtrack(index: int):
            if index == len(S):
                return len(ans) >= 3
            curr = 0
            for i in range(index, len(S)):
                if i > index and S[index] == "0":
                    break
                curr = curr * 10 + ord(S[i]) - ord("0")
                if curr > 2**31 - 1:
                    break
                if len(ans) < 2 or curr == ans[-2] + ans[-1]:
                    ans.append(curr)
                    if backtrack(i + 1):
                        return True
                    ans.pop()
                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:
                    break
            return False
        backtrack(0)
        return ans