###### tags: `LeetCode` `Medium` `DFS` `String`
# LeetCode #842 [Split Array into Fibonacci Sequence](https://leetcode.com/problems/split-array-into-fibonacci-sequence/)
### (Medium)

給定一個數字字符串 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 拆分出來的任意一組斐波那契式的序列塊，如果不能拆分則返回 [ ]。

---
因為題目規定元素值最大為 2^31 - 1, 因此每個數最大可達10位數(最小1位數)。

遞迴的中止條件為索引值等同於字串s的大小, 此時若斐波那契數組的大小大於等於3, 則回傳true, 小於3則回傳false(至少要3個數才能組成一斐波那契數組)。

接下來, 若數字字串的第一個數字為0, 則該次數字只能取一位數(0), 因為不能出現05、012等組合; 而若第一個數字不為0, 則最多可以取10位數(如前面所提), 使用for迴圈模擬取1-10位數的組合, 而若暫存斐波那契數組的大小大於等於2, 則當次迴圈所取的值必須等於目前數組中的倒數第一與倒數第二個值的和, 而若索取的數字大於斐波那契和, 則終止(break)該迴圈(因為再後面更多位數的值全部都會大於斐波那契和), 而若所取的值小於和, 則跳過該輪。

在經過判斷式篩選後, 可以保證所取的值恰好等於斐波那契和, 此時將其存入暫存數組中, 並以目前位置+1作為所以遞迴呼叫, 尋找下一個斐波那契數。而遞迴結束後將暫存數組的最後一個值彈出。

假若全部迴圈結束時仍然沒有回傳true, 則回傳false。

---

class Solution {
public:
    vector<int> splitIntoFibonacci(string s) {
        int n=s.size();
        vector<int> nums;
        function<bool(int)> dfs = [&](int pos){
            if(pos==n)return nums.size()>=3;
            int maxlength = s[pos]=='0'?1:10;
            long num = 0;
            for(int i=pos;i<min(n, pos+maxlength);i++){
                num = num*10+(s[i]-'0');
                if(num>INT_MAX)break;
                if(nums.size()>=2){
                    long sum = nums.rbegin()[0];
                    sum+=nums.rbegin()[1];
                    if(num>sum)break;
                    else if(num<sum)continue;
                }
                nums.push_back(num);
                if(dfs(i+1))return true;
                nums.pop_back();
            }
            return false;
        };
        dfs(0);
        return nums;
    }
};