# 842. Split Array into Fibonacci Sequence (medium)
###### tags: `online_judge`, `python3`

隱藏地雷的 medium 題。把給定的數字分割成類費氏數列。

使用暴力列舉前兩個數字的所有長度可能性即可，考量至少需要 3 個數字組成，可以多少縮減長度範圍。

需要注意 3 點：

1. 第 2 個數字長度可以比第 1 個數字短，這跟 Fibonacci Sequence 不一樣。
2. 不容許以零為首的數字，例如```02```。單一個零，即```0```則例外。
3. ***數列中所有數字範圍都必須在 32-bit int 內。***

第三點沒注意就會坑死 python 用家...　寫 C 的話倒大概是不受影響（因為你會 overflow，LOL）。

---
### 題目

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

    0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
    F.length >= 3;
    and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

    1 <= S.length <= 200
    S contains only digits.

---

### 解答

class Solution:
    
    def is_lead_zero(self,S):
        if len(S)>1 and S[0]=='0':
            return True
        else:
            return False
		
    def is_fib(self,S,fount,back):
        
        output = []
        output.append(fount)
        output.append(back)
        ans = str(int(fount) + int(back))
        
        start = len(fount) + len(back)
        end = start + len(ans)
        
        if S[start:end] != ans or int(ans)>2147483647:
            output = []
            return output
        
        output.append(ans)
        
        while end<len(S):
            fount = back
            back = ans
            ans = str(int(fount) + int(back))

            start = end
            end = start + len(ans)

            if S[start:end] != ans or int(ans)>2147483647:
                output = []

                return output
            output.append(ans)
        return output
            
    
    def splitIntoFibonacci(self, S: str):
        
        
        for i in range(1,int(len(S))):
            fount = S[0:i]
            if self.is_lead_zero(fount) == True:
                continue
				
            for j in range(1,int(len(S))):
                if i + j > int(len(S)/3)*2+1:
                    continue
                output = []

				
                back = S[i:i+j]
                if self.is_lead_zero(back) == True:
                    continue
                
                output = self.is_fib(S,fount,back)
                if output:
                    return output
		
        empty = []
        return empty
        
a = Solution()
print (a.splitIntoFibonacci("0123"))

---

### 成績


---