leetcode842 将数组拆成斐波那契数列

题目

将数组拆成斐波那契数列

分析

这道题的思路就是dfs，是男人就该暴力搜索嘛。
要注意的点有以下几个：

• 0怎么处理？0先按照位置划分有两种情况，一是在字符串首，二是在字符串的中间，在字符串首时因为0不能作为数的开头，那么字符串首的0就只能作为一个单独的数。在字符串中间的情况又分为两种，一是放在在一段字符串的首位置，举个例子："12304"这个字符串，当前面的123已经作为一个或几个单独的数了，那么这个时候剩下的字符串只有"04"，这个时候的0只能作为一个单独的数，还有一种情况就是把0当作一个普通的数，跟其他数用法一样。

• 题目告知了数列里的每个数都在int范围，所以当算得一个数不在int范围的时候，那么就可以反悔了，这条搜索路径一定走不通。并且不能用a + b == c的方式判断斐波那契数列，因为a + b可能已经溢出了，所以要用c - a = b的方式来判断。

代码

class Solution {
private:
    vector<int> res;
    void dfs(long long cur, int k, string s, vector<int>& vec) {
        if (!res.empty() || k > s.size()) {
            return;
        }
        long long n = vec.size();
        if (k == s.size() && n >= 3 && vec[n - 2] + vec[n - 3] == vec[n - 1]) {
            res = vec;
            return;
        }

        for (long long i = k; res.empty() && i < s.size(); i++) {
            if (cur == 0 && s[i] == '0') {
                if (n == 0) {
                    vec.push_back(0);
                    dfs(0, i + 1, s, vec);
                } else if (n < 2 || vec[n - 2] + vec[n - 1] == cur) {
                    vec.push_back(0);
                    dfs(0, i + 1, s, vec);
                    vec.pop_back();
                }
            } else {
                cur = cur * 10 + (s[i] - '0');
                if (cur < 0 || cur > (long long)INT_MAX) {
                    break;
                }
                if (n < 2 || vec[n - 2] == cur - vec[n - 1]) {
                    vec.push_back(cur);
                    dfs(0, i + 1, s, vec);
                    vec.pop_back();
                }
            }
        }
    }
public:
    vector<int> splitIntoFibonacci(string S) {
        vector<int> vec;

        dfs(0, 0, S, vec);
        if (res.empty()) {
            return {};
        }
        return res;
    }
};