类型：字符串
-
- 将数组拆分成斐波那契序列 💛
https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/
❓ 给定一个数字字符串 S，比如 S = “123456579”，我们可以将它分成斐波那契式的序列 [123, 456, 579]。返回拆分后的数组，若不能则返回空数组。
💡 回溯 + 剪枝
从第 3 个数开始，每个数都等于前 2 个数的和，因此从第 3 个数开始，需要判断拆分出的数是否等于前 2 个数的和，只有满足要求时才进行拆分，否则不进行拆分。
回溯过程中，还有三处可以进行剪枝操作。
- 拆分出的数如果不是 0，则不能以 0 开头，因此如果字符串剩下的部分以 0 开头，那么只能考虑 0.
- 拆分出的数必须符合 32 位有符号正整数类型，即每个数必须在[0,2^31-1] 的范围内。
- 如果列表中至少有 22 个数，并且拆分出的数已经大于最后 22 个数的和，就不需要继续尝试拆分了。
回溯需要带返回值，表示是否存在符合要求的斐波那契式序列。
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