将数组拆分成斐波那契序列

题解通过使用回溯法来尝试构建斐波那契序列。首先定义一个辅助函数 dfs(i)，其中 i 表示当前正在处理的数字的起始位置。如果 i 等于字符串的长度且答案列表中至少有三个数，说明已经成功构建了一个序列，函数返回 True。然后逐个检查可能的数字，如果遇到以 '0' 开头的数字（并且长度超过1），则跳出循环。对每一个可能的数字，检查是否符合斐波那契序列的要求：1) 数字不能超过 2^31 - 1；2) 如果列表中已有至少两个数，该数必须等于最后两个数的和。如果当前数字满足要求，将其加入到序列中并递归调用 dfs(j+1)。如果递归调用返回 True，表示找到了合法的序列，当前函数也返回 True。如果当前路径不行，则将最后一个数字从序列中移除（回溯），尝试下一个可能的数字。如果所有可能都尝试完毕，返回 False。

时间复杂度: O(2^n)

空间复杂度: O(n)

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        def dfs(i):
            if i == n:
                return len(ans) > 2  # 当处理完整个字符串且答案序列长度大于2时，返回True
            x = 0
            for j in range(i, n):
                if j > i and num[i] == '0':
                    break  # 跳过以0为开头的数字（除非它自身是0）
                x = x * 10 + int(num[j])  # 将当前字符转为数字并添加到当前数 x
                if x > 2**31 - 1 or (len(ans) > 2 and x > ans[-2] + ans[-1]):
                    break  # 如果 x 太大或不符合斐波那契规则，则终止当前循环
                if len(ans) < 2 or ans[-2] + ans[-1] == x:
                    ans.append(x)  # 将 x 添加到当前答案序列中
                    if dfs(j + 1):
                        return True  # 递归地尝试下一位置，如果成功，则直接返回True
                    ans.pop()  # 如果不成功，回溯，移除 x
            return False  # 如果所有尝试都不成功，返回False

        n = len(num)
        ans = []  # 初始化答案列表
        dfs(0)
        return ans  # 返回最终答案，可能为空列表