题目描述

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

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

0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
F.length >= 3；
对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

样例

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

算法

(暴力枚举) $O(n^2)$

用DFS搜索字符串，前两个数需要逐个尝试，后面的数只枚举符合条件的数。

时间复杂度

O(n)

C++ 代码

class Solution {
public:
    vector<int> splitIntoFibonacci(string S){
        vector<int> nums;
        const int n = S.size();
        function<bool(int)> dfs = [&](int pos){
            if(pos == n) return nums.size() > 2;//如果小于等于2代表只有前两个数，没有第三个数，失败
            long num = 0;//当前要计算的数
            int max_len = S[pos] == '0' ? 1:10;//数不可以有前导零
            int end = min(max_len + pos, n);
            for(int i = pos; i < end; i++){
                num = num * 10 + S[i] - '0';
                if(num > INT_MAX) break;//题设是满足INT32类型的整数，如果num超过INT_MAX，失败
                if(nums.size() > 1){//nums中已经有两个数了，检查是否符合结果。
                    long sum = nums.rbegin()[0];//不知道为什么，这样要比直接相加快，注意直接相加要进行类型转换
                    sum += nums.rbegin()[1];
                    if(num > sum) break; //num已经超过了前两个数之和，不需要继续枚举后面的数了，失败
                    else if(num < sum) continue;//num小于sum，继续
                }
                nums.push_back(num);//num==sum或者还在枚举前两个数
                if(dfs(i + 1)) return true;//成功
                else nums.pop_back();//失败，继续枚举
            }
            return false;
        };

        dfs(0);
        return nums;
    }
};