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.

Difficulty: interview

Starter code:

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        

Solutions:
class Solution(object):
    def splitIntoFibonacci(self, S):
        \"\"\"
        :type S: str
        :rtype: List[int]
        \"\"\"
        n = len(S)
        for i in range(1, 11):
            for j in range(1, 11):
                if i + j >= n:
                    break
                L = self.buildFibo(S, i, j)
                if L:
                    return L
        return []
    
    def buildFibo(self, s, i, j):
        a = s[:i]
        b = s[i:i+j]
        if a[0] == '0' and i > 1:
            return []
        if b[0] == '0' and j > 1:
            return []
        
        offset = i + j
        n = len(s)
        x, y = int(a), int(b)
        arr = [x, y]
        while offset < n:
            z = x + y
            if z > 2147483647:
                return []
            
            c = str(z)
            k = len(c)
            if offset + k > n or s[offset:offset+k] != c:
                return []
            offset += k
            arr.append(z)
            x, y = y, z
        return arr

class Solution:
    def splitIntoFibonacci(self, S):
        for i in range(min(10, len(S))):
            x = S[:i+1]
            if x != '0' and x.startswith('0'): break
            a = int(x)
            for j in range(i+1, min(i+10, len(S))):
                y = S[i+1: j+1]
                if y != '0' and y.startswith('0'): break
                b = int(y)
                fib = [a, b]
                k = j + 1
                while k < len(S):
                    nxt = fib[-1] + fib[-2]
                    nxtS = str(nxt)
                    if nxt <= 2**31 - 1 and S[k:].startswith(nxtS):
                        k += len(nxtS)
                        fib.append(nxt)
                    else:
                        break
                else:
                    if len(fib) >= 3:
                        return fib
        return []

class Solution:
    def splitIntoFibonacci(self, S: str):
        self.res = []
        self.dfs(S, [], 0)
        return self.res
    
    def dfs(self, S, temp, count):
        if not S and count >= 3:
            self.res = temp[:]
            return
        for step in range(1, min(len(S)+1, 11)):
            val = S[:step]
            if str(int(val)) == val and 0 <= int(val) <= pow(2, 31) - 1: # 防止前导 0 的出现
                if count < 2:
                    temp.append(int(val))
                    self.dfs(S[step:], temp, count+1)
                    temp.pop()
                elif temp[count-2] + temp[count-1] == int(val):
                    temp.append(int(val))
                    self.dfs(S[step:], temp, count+1)
                    temp.pop()

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def backtrack(path=[], i=0):
            if i == len(S): return path if len(path) >= 3 else []
            for j in range(i+1, min(i+10, len(S)) + 1):
                if S[i] == '0' and j > i + 1: continue
                x = int(S[i:j])
                if x < 2**31 and (len(path) < 2 or (len(path) >= 2 and x == sum(path[-2:]))):
                    new = backtrack(path + [x], j)
                    if new: return new
            return []
        
        return backtrack()

class Solution:
    def dfs(self,final,S,path,original):
        #print(path)
        if not S and len(path)>2 and all([int(i)<=2**31 - 1 for i in path]):
            final.append(path)
        for i in range(1,len(S)+1):
            temp = int(S[:i])
            if i>1 and S[:i][0]=='0': continue
            if int(S[:i])>=2**31 - 1 : return
            if len(path)<2 or (len(path)>=2 and int(path[-1])+int(path[-2])==temp ):
                self.dfs(final,S[i:],path+[S[:i]],original)
                
    def splitIntoFibonacci(self, S: str) -> List[int]:
        final = []
        path = []
        self.dfs(final,S,path,S)
        if final : return final[0]
        return []

'''
I think Idea is to consider for all possible starting pairs (so number1,startingIndex1,number2,startingIndex2), what is longest pair we can get moving forward
'''
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        BIG_NUMBER = 2**31-1##python can interpret long numbers so we will use this to compute.
        numSplits = {}##tells what the number is represented by the substring from a to b b exclusive.
        sLength = len(S)
        reverseSplits = {}
        for i in range(sLength):
            currentNum = 0
            for j in range(i+1,sLength+1):
                currentNum *= 10
                currentNum += int(S[j-1])
                if currentNum == 0:
                    numSplits[(i,j)] = currentNum
                    if currentNum not in reverseSplits:
                        reverseSplits[currentNum] = {}
                    if i not in reverseSplits[currentNum]:
                        reverseSplits[currentNum][i] = set([j])
                    else:
                        reverseSplits[currentNum][i].add(j)
                    break
                elif currentNum > BIG_NUMBER:
                    break
                else:
                    numSplits[(i,j)] = currentNum
                    if currentNum not in reverseSplits:
                        reverseSplits[currentNum] = {}
                    if i not in reverseSplits[currentNum]:
                        reverseSplits[currentNum][i] = set([j])
                    else:
                        reverseSplits[currentNum][i].add(j)
        fibonacciSequences = {}
        def computeFibonacciSequences(startingIndex):##if startingIndex == 
            if startingIndex not in fibonacciSequences:
                if startingIndex == sLength:
                    answer = [[]]
                else:
                    answer = []
                    for i in range(startingIndex+1,sLength+1):
                        if (startingIndex,i) in numSplits:##so this is a valid number.
                            nextNumber = numSplits[(startingIndex,i)]
                            ithFibonaccis = computeFibonacciSequences(i)
                            for fibSeq in ithFibonaccis:
                                if len(fibSeq) > 1:
                                    largeNumber = fibSeq[-2]
                                    smallNumber = fibSeq[-1]
                                    if nextNumber == largeNumber-smallNumber:
                                        appended = fibSeq+[nextNumber]
                                        answer.append(appended)
                                else:
                                    appended = fibSeq + [nextNumber]
                                    answer.append(appended)
                        else:
                            break
                fibonacciSequences[startingIndex] = answer
                return answer
            else:
                return fibonacciSequences[startingIndex]
        computeFibonacciSequences(0)
        for sequence in fibonacciSequences[0]:
            if len(sequence) >= 3:
                sequence.reverse()
                return sequence
        else:
            return []

                                    
                                


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def f(l, i):
            if i == len(S) and len(l) >= 3:
                return l
            r = []
            t = 0
            for j in range(i, len(S)):
                t *= 10
                t += int(S[j])
                if t <= 2**31 - 1:
                    if len(l) > 1 and l[-1] + l[-2] != t:
                        continue
                    l.append(t)
                    temp = f(l, j + 1)
                    if temp:
                        return temp
                    l.pop()
                    if t == 0:
                        return []
            return r
        return f([], 0)       

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
                
            
        n = len(S)
        
        for i in range(1, min(32, (n-1)//2+1)):
            for j in range(i+1, 2 * n//3 + 1):
                a, b = int(S[:i]), int(S[i:j])
                idx = len( str(a+b) )
                tmp = [a, b]
                l = j
                while int(S[l:l+idx]) == a+b:
                    if int(S[l:l+idx]) > 2 ** 31 - 1:
                        break
                    tmp.append( int(S[l:l+idx]) )
                    if l + idx == n:
                        return tmp
                    a = b
                    b = int(S[l:l+idx])
                    l += idx
                    idx = len(str(a+b))
        return []
        


class Solution:
    def trysolve(self, s, seq, n):
        seq.append(n)
        if self.solve(s, seq):
            return True
        seq.pop()
        return False
       
    def solve(self, s, seq):
        if not s:
            return True
        target = sum(seq[-2:])
        if target > 2 ** 31 - 1:
            return False
        if s[0] == '0':
            if target == 0:
                return self.trysolve(s[1:], seq, 0) ;
            else:
                return False
        for end in range(1, len(s)+1):
            n = int(s[:end])
            if n == target and self.trysolve(s[end:], seq, n):
                return True
        return False       
     
    def splitIntoFibonacci(self, S: str) -> List[int]:
        limit = 2**31 - 1;
        for i in range(1, len(S)):
            n1 = int(S[:i]);
            if(n1>limit):
                return [];
            if(n1!=0 and S[0]=='0'):
                return [];
            for j in range(i+1, len(S)):
                n2 = int(S[i:j])
                if n2 != 0 and S[i] == '0':
                    break
                if n2 > limit:
                    break 
                seq = [n1, n2]
                if self.solve(S[j:], seq):
                    return seq;
        return []
                
            


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def f(l, i, leng):
            if leng == len(S) and len(l) >= 3:
                return l
            r = []
            t = 0
            for j in range(i, len(S)):
                t *= 10
                t += int(S[j])
                leng += 1
                if t <= 2**31 - 1:
                    if len(l) > 1 and l[-1] + l[-2] != t:
                        continue
                    l.append(t)
                    temp = f(l, j + 1, leng)
                    if temp:
                        return temp
                    l.pop()
                    if t == 0:
                        return []
            print(r)
            return r
        return f([], 0, 0)       

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        #backtrack way
        n, ans = len(S), []


        def dfs(pos):
            if pos == n:
                return len(ans) >= 3
        
            num = 0
            for i in range(pos, n):
                if (S[pos] == '0' and i == pos) or S[pos] != '0':
                    num = num * 10 + ord(S[i]) - ord('0')
                    if num < 2 ** 31 - 1:
                        if len(ans) < 2 or (ans[-1] + ans[-2] == num):
                            ans.append(num)
                            if dfs(i + 1):
                                return True #end early
                            ans.pop()
            return False
        dfs(0)
        return ans
        
# iteration
#         l = len(S)
#         m = 2 ** 31 - 1
#         for i in range(1, l):
#             if S[0] == '0' and i != 1:
#                 break
                
#             for j in range(i + 1, l):
#                 if S[i] == '0' and j != i + 1:
#                     break
                        
#                 pre = int(S[:i])
#                 cur = int(S[i:j])
#                 res = [pre, cur]

#                 k = j
#                 while k < l:
#                     pre, cur = cur, pre + cur
#                     if cur <= m and int(S[k:k+len(str(cur))]) == cur:
#                         res.append(cur)
#                         k += len(str(cur))
#                     else:
#                         break
#                 if k == l and len(res) >= 3:
#                     return res
#         return []
                        


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def startswith(S, k, x):
            y = 0
            for i in range(k, len(S)):
                y = 10*y + int(S[i])
                if y == x:
                    return i-k+1
                elif y > x:
                    break
            return 0

        MAX_INT = 2**31-1
        a = 0
        for i in range(len(S)-2):
            a = 10*a + int(S[i])
            b = 0
            for j in range(i+1, len(S)-1):
                b = 10*b + int(S[j])
                fib = [a, b]
                k = j+1
                while k < len(S):
                    if fib[-2] > MAX_INT-fib[-1]:
                        break
                    c = fib[-2]+fib[-1]
                    length = startswith(S, k, c)
                    if length == 0:
                        break
                    fib.append(c)
                    k += length
                else:
                    return fib
                if b == 0:
                    break
            if a == 0:
                break
        return []
                


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        exp = 2**31 - 1
        def works(x,y,i):
            res = [x,y]
            while i < len(S):
                target = res[-2] + res[-1]
                if target > exp:
                    return []
                build = S[i]
                i += 1
                while i < len(S) and build < target:
                    if build == 0:
                        return []
                    build = build*10 + S[i]
                    i += 1
                if build != target:
                    return []
                res.append(build)
            return res
        S = [int(c) for c in S]
        N = len(S)
        x = 0
        for i in range(N-2):
            if i > 0 and x == 0:
                break
            x = x*10 + S[i]
            y = 0
            for j in range(i+1, N-1):
                if j > i+1 and y == 0:
                    break
                y = y*10 + S[j]
                res = works(x,y,j+1)
                if res: return res
            
        return []

class Solution:
  def dfs(self, grandpa, parent, S, start):
    # return the fibonacci seqs of S[start:] given grandpa and parent
    if start >= len(S):
      return [], True
    for i in range(start+1, len(S)+1):
      sub = S[start: i]
      if len(sub) > 1 and sub[0] == '0':
        # invalid
        continue
      num = int(sub)
      if num > 2**31 - 1:
        continue
      if grandpa >= 0 and parent >= 0 and num != grandpa + parent:
        continue
        
      ans, found = self.dfs(parent, num, S, i)
      if grandpa < 0 and parent < 0 and len(ans) < 2:
        continue
      if found:
        return [num] + ans, True
    return [], False
  
  def splitIntoFibonacci(self, S: str) -> List[int]:
    return self.dfs(-1, -1, S, 0)[0]

class Solution:
    def splitIntoFibonacci(self, S) :
        self.res=[]
        def dfs(index,prev2,prev,count,cur_path):
            if index==len(S) and count>=3:
                self.res=cur_path
                return

            for i in range(index,len(S)):
                x=int(S[index:i+1])
                if count==0:
                    dfs(i+1,0,x,count+1,cur_path+[x])

                else:
                    if x>(1<<31):
                        return False
                    if x==prev2+prev or count==1:
                        if dfs(i + 1, prev, x, count + 1, cur_path + [x]):
                            return True
                if x==0:
                    break


        dfs(0,0,0,0,[])
        return self.res

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        if len(S) < 3: return []
        
        def dfs(S, path):
            if not S:
                if len(path) >= 3:
                    return path
                return []
                
            for l in range(1, len(S) + 1):
                if (len(S[:l]) > 1 and S[0] == \"0\") or (int(S[:l]) > 2**31 -1):
                    continue 
                    
                if len(path) < 2:
                    temp = dfs(S[l:], path + [int(S[:l])])
                    if temp:
                        return temp
                    
                else:
                    if path[-1] + path [-2] == int(S[:l]):
                        temp = dfs(S[l:], path + [int(S[:l])])
                        if temp:
                            return temp
            return []
        
        return dfs(S, [])
                
                        
            

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def check(i, a, b):
            if int(a) > 2147483647 or int(b) > 2147483647:
                return [], False
            if i == len(S):
                return [str(a), str(b)], True
            s = str(a + b)
            if S[i: i + len(s)] == s:
                out, good = check(i + len(s), b, int(s))
                if good:
                    return [str(a)] + out, True
            return [], False
                
        for i in range(len(S) - 2):
            a = int(S[:i+1])
            if S[0] == '0' and a != 0:
                break
            for j in range(i + 1, len(S) - 1):
                b = int(S[i + 1: j + 1])
                if S[i + 1] == '0' and b != 0:
                    break
                out, _ = check(j + 1, a, b)
                if out:
                    return out
        return []
                
                


class Solution(object):
    def splitIntoFibonacci(self, S):
        \"\"\"
        :type S: str
        :rtype: List[int]
        \"\"\"
        def backtrack(cur, temp_state):
            if len(temp_state) >= 3 and cur == n:  # 退出条件
                self.res = temp_state[:]
                return
            for i in range(cur, n):
                if S[cur] == \"0\" and i > cur:  # 当数字以0开头时,应该跳过
                    return
                if int(S[cur: i+1]) > 2 ** 31 - 1 or int(S[cur: i+1]) < 0:  # 剪枝
                    continue
                if len(temp_state) < 2:
                    backtrack(i+1, temp_state + [int(S[cur: i+1])])
                else:
                    if int(S[cur: i+1]) == temp_state[-1] + temp_state[-2]:
                        backtrack(i+1, temp_state + [int(S[cur: i+1])])

        n = len(S)
        self.res = []
        backtrack(0, [])
        return self.res
        

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        def helper(a, i, j, cur_ans):
            if S[i]=='0' and j!=i+1:
                cur_ans=[]
                return False
            if a>2**31-1:
                return False
            b=int(S[i:j])
            c=a+b
            if b>2**31-1 or c>2**31-1:
                return False
            c_s=str(c)
            if c_s==S[j:j+len(c_s)]:
                k=j+len(c_s)
                cur_ans.append(c)
                if k==len(S):
                    return True
                if helper(b, j, k, cur_ans):
                    return True
                else:
                    cur_ans=[]
                    return False
            cur_ans=[]
            return False
        if len(S)==0:
            return []
        
        for i in range(1, len(S)):
            
            if i>1 and S[0]=='0':
                break
            a=int(S[:i])
            for j in range(i+1, len(S)):
                cur_ans=[a, int(S[i:j])]
                if helper(a, i, j, cur_ans):
                    return cur_ans
        
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans=0
        def helper(pp,p,i,no):
            nonlocal ans
            if(i==len(S) and len(no)>=3):
                ans=no
                return True
            else:
                for j in range(i+1,len(S)+1):
                    ok=S[i:j]
                    if(ok[0]==\"0\" and len(S[i:j])>1):
                        continue
                    if(int(S[i:j])>(2**31)-1):
                        continue
                    let=int(S[i:j])
                    if(pp==-1):
                        if(helper(let,p,j,no+[let])):
                            return True
                    elif(p==-1):
                        if(helper(pp,let,j,no+[let])):
                            return True
                    else:
                        if(let==pp+p):
                            if(helper(p,let,j,no+[let])):
                                return True
            return False
        if(helper(-1,-1,0,[])==False):
            return []
        else:
            return ans
                

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        for i in range(len(S))[::-1]:
            for j in range(i+1,len(S)):
                b,c = int(S[i:j]), int(S[j:])
                if c >= 2**31: continue
                if b >= 2**31: continue

                parts = [b,c]
                a = c-b
                while a >= 0 and a <= 2**31 - 1:
                    parts.insert(0, a)
                    b,c = a,b
                    a = c-b

                    if S == ''.join(map(str,parts)):
                        return parts
        
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = []
        limit = 2**31 - 1
        def helper(n, prefix):
            nonlocal S, ans
            if ans:
                return
            if n == len(S):
                ans = prefix
                return
            num = sum(prefix[-2:])
            if S[n:].startswith(str(num)) and num <= limit:
                return helper(n + len(str(num)), prefix + [num])
        for i in range(2, len(S) * 2 // 3 + 1):
            for j in range(1, i):
                helper(i, [int(S[:j]), int(S[j:i])])
                if ans:
                    break
            if ans:
                break
        return ans

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        ans = []
        
        def dfs(position):
            # means at end of string
            if position == n:
                return True if len(ans) > 2 else False
            
            num = 0
            
            for i in range(position, n):
                # build number from string
                num = num * 10 + ord(S[i]) - ord('0')
                
                # check for integer overflow
                if num >= 2**31:
                    break
                    
                # check len and last elem in ans + 2nd to last elem in ans = num
                if len(ans) < 2 or ans[-1] + ans[-2] == num:
                    # add to ans, start of backtracking portion
                    ans.append(num)
                    # recurse on next index, if true return true
                    if dfs(i+1):
                        return True
                    # pop recently add num from ans
                    ans.pop()
                
                # check for trailing/leading 0s and i == position
                if i == position and S[i] == '0':
                    return False
            
            return False
        # call
        dfs(0)
        return ans

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        def impl(s, pos, output):
            if pos >= len(s):
                return len(output) >= 3
            loop_end = len(s) + 1
            if s[pos] == '0':
                loop_end = pos + 2
            for p in range(pos + 1, loop_end):
                this_number = int(s[pos:p])
                if this_number > pow(2, 31) - 1:
                    continue
                if len(output) >= 2 and output[-1] + output[-2] == this_number:
                    output.append(this_number)
                    if impl(s, p, output):
                        return True
                    else:
                        output.pop()
                elif len(output) < 2:
                    output.append(this_number)
                    if impl(s, p, output):
                        return True
                    else:
                        output.pop()
            return False
        
        result = []
        impl(S, 0, result)
        
        return result


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = []
        limit = 2**31 - 1
        def helper(n, prefix):
            nonlocal S, ans
            if ans:
                return
            if n == len(S):
                ans = prefix
                return
            num = sum(prefix[-2:])
            if S[n:].startswith(str(num)) and num <= limit:
                return helper(n + len(str(num)), prefix + [num])
        for i in range(2, len(S) * 2 // 3 + 1):
            for j in range(1, i):
                helper(i, [int(S[:j]), int(S[j:i])])
        return ans

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = []
        limit = 2**31 - 1
        
        @lru_cache(None)
        def helper(n, prefix):
            nonlocal S, ans
            if n == len(S):
                ans = prefix
                return
            num = int(S[prefix[-2]:prefix[-1]]) + int(S[prefix[-1]:n])
            if S[n:].startswith(str(num)) and num <= limit:
                return helper(n + len(str(num)), prefix + (n,))
            
        for i in range(2, len(S) * 2 // 3 + 1):
            for j in range(1, i):
                helper(i, (0, j))
                if ans:
                    break
            if ans:
                break
        return [int(S[i:j]) for i, j in zip(ans, ans[1:] + (len(S),))] if ans else []


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = []
        dfs(S, [], ans)
        return ans[0] if ans else []

        
def dfs(S, temp, ans):
    # print(S)
    # print(temp)
    if len(temp) >= 3 and not is_valid_fibonacci(temp):
        return
    if S == \"\":
        if len(temp) >= 3:
            ans.append(temp.copy())
        return 
    for i in range(1, len(S) + 1):
        sub_str = S[:i]
        rest_str = S[i:]
        # '01' is not allowed
        if sub_str.startswith('0') and len(sub_str) != 1:
            continue
        num = int(sub_str)
        # 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
        if num < 0 or num > 2 ** 31 - 1:
            continue
        # print(sub_str)
        # print(rest_str)
        temp.append(num)
        dfs(rest_str, temp, ans)
        temp.pop()
        
def is_valid_fibonacci(items):
    # check last 3 elements
    return items[-1] == items[-2] + items[-3]
        

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        b = []
        c = []
        def additivenumber(num,b):
            if len(c) == 1:
                return \"\"
            if len(b) > 2 and num == \"\":
                c.append(b)
            else:
                for x in range(len(num)):
                    if len(num[0:x+1]) == 1:
                        if len(b) >= 2:
                            if int(num[0:x+1]) == b[-1] + b[-2]:
                                additivenumber(num[x+1:],b+[int(num[0:x+1])])
                        else:
                            additivenumber(num[x+1:],b+[int(num[0:x+1])])
                    else:
                        if num[0:x+1][0] != str(0) and int(num[0:x+1]) <= 2147483647:
                            if len(b) >= 2:
                                if int(num[0:x+1]) == b[-1] + b[-2]:
                                    additivenumber(num[x+1:],b+[int(num[0:x+1])])
                            else:
                                additivenumber(num[x+1:],b+[int(num[0:x+1])])
        additivenumber(num,b)
        if c == []:
            return c
        return c[0]
        

class Solution:
    def splitIntoFibonacci(self, S):
        \"\"\"
        :type S: str
        :rtype: List[int]
        \"\"\"
        limit=2**31 - 1
        for i in range(1,len(S)):
            if S[0]==\"0\" and i!=1:
                break
            for j in range(i+1,len(S)):
                if S[i]==\"0\" and j!=i+1:
                    break
                pre=int(S[:i])
                cur=int(S[i:j])
                ans=[pre,cur]
                k=j
                while k<len(S):
                    cur,pre=pre+cur,cur
                    if cur<=limit and str(cur)==S[k:k+len(str(cur))]:
                        ans.append(cur)
                        k=k+len(str(cur))
                    else:
                        break
                if k==len(S):
                    return ans
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans=0
        c=(2**31)-1
        def helper(pp,p,i,no):
            nonlocal ans
            if(i==len(S) and len(no)>=3):
                ans=no
                return True
            else:
                for j in range(i+1,len(S)+1):
                    ok=S[i:j]
                    if(ok[0]==\"0\" and len(S[i:j])>1):
                        continue
                    if(int(S[i:j])>c):
                        continue
                    let=int(S[i:j])
                    if(pp==-1):
                        if(helper(let,p,j,no+[let])):
                            return True
                    elif(p==-1):
                        if(helper(pp,let,j,no+[let])):
                            return True
                    else:
                        if(let==pp+p):
                            if(helper(p,let,j,no+[let])):
                                return True
            return False
        if(helper(-1,-1,0,[])==False):
            return []
        else:
            return ans
                

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        
        def dfs(index,res,s): 
            #print(res)
            if index == len(s) and len(res)>=3:
                return True
            num = 0 
            for i in range(index,len(s)):
                num = num * 10 + (ord(s[i]) - ord('0'))
                if num > 2**31-1:
                    break
                if len(res)>2 and  (num > res[-1]+res[-2]):
                    break
                if s[index] == '0' and i > index:
                    break
                if len(res) < 2 or (res[-1]+res[-2] == num):
                    res.append(num)       
                    if dfs(i+1,res,s):
                        return True
                    res.pop()
                
            return False
        result = []
        dfs(0,result,S)
        return result
                
                
            


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        if len(S) < 2: return []
    
        def dfs(s, path):
            if not s:
                if len(path) >= 3:
                    return path
                return []

            for  i in range(len(s)):
                if (len(s[:i+1]) > 1 and s[0]==\"0\") or int(s[:i+1]) > 2**31-1:
                    continue 
                if len(path) < 2:
                    tmp = dfs(s[i+1:], path + [s[:i+1]])
                    if tmp:
                        return tmp
                else:
                    if int(path[-2]) + int(path[-1]) == int(s[:i+1]):
                        tmp = dfs(s[i+1:], path +[s[:i+1]])
                        if tmp:
                            return tmp
            return []
        
        return dfs(S,[])

class Solution:
    def ok(self, S, j, res):
        # print(j, res)
        if j == len(S):
            return True        
        for k in range(j + 1, len(S) + 1):
            third = S[j:k]
            if len(third) > 1 and third[0] == '0' or int(third) >= 2 ** 31:
                continue                
            third = int(third)
            if third  == res[-1] + res[-2]:
                res.append(third)
                if self.ok(S, k, res):
                    return True
                else:
                    res.pop()
        return False
    
    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        res = []
        for i in range(1, n - 1):
            first = S[0:i]
            if len(first) > 1 and first[0] == '0' or int(first) >= 2 ** 31:
                continue            
            for j in range(i + 1, n):
                second = S[i:j]
                if len(second) > 1 and second[0] == '0' or int(second) >= 2 ** 31:
                    continue                
                res = [int(first), int(second)]
                if self.ok(S, j, res):
                    return res
                else:
                    res = []
        return res

class Solution:
    
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def helper(S: str, curr_path: List[int]):
            if not S:
                if self.isValidPath(curr_path):
                    return curr_path
                return None
            
            
            for partition_point in range(1, len(S)+1):
                prefix, suffix = S[:partition_point], S[partition_point:]
                valid_prefix = prefix == '0' or prefix[0] != '0' and int(prefix) <= (2**31-1)
                new_curr_path = curr_path + [int(prefix)]
                if valid_prefix and (len(new_curr_path) < 3 or self.isValidPath(new_curr_path)):
                    recurse = helper(suffix, new_curr_path)
                    if recurse:
                        return recurse
            return None
            
        return helper(S, [])
    
    def isValidPath(self, path: List[str]) -> bool:
        return len(path) > 2 and int(path[-1]) == (int(path[-2]) + int(path[-3]))
        
    


from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256


def split(f1, f2, si, S):
    N = len(S)
    if N <= si:
        return []
    prefixNum = f1 + f2
    if prefixNum >= (1 << 31):
        return []
    prefixS = str(f1 + f2)

    if S[si] == '0':
        if prefixNum > 0:
            return []
        else:
            if si == N - 1:
                return [0]
            else:
                tail = split(f2, 0, si + 1, S)
                if len(tail):
                    tail.append(0)
                    return tail
                else:
                    return []

    else:
        nextSi = si + len(prefixS)
        if nextSi <= N and S[si:nextSi] == prefixS:
            if nextSi == N:
                return [prefixNum]
            else:
                #print(\"split!!\")
                tail = split(f2, prefixNum, si + len(prefixS), S)
                if len(tail):
                    tail.append(prefixNum)
                    return tail
    return []


class Solution:

    def splitIntoFibonacci(self, S: str) -> List[int]:
        N = len(S)
        for firstEI in range(N - 2):
            if S[0] == '0' and firstEI > 0:
                continue
            firstN = int(S[:firstEI + 1])
            for secondEI in range(firstEI + 1, N - 1):
                if S[firstEI + 1] == '0' and secondEI > firstEI + 1:
                    continue
                secondN = int(S[firstEI + 1:secondEI + 1])

                tail = split(firstN, secondN, secondEI + 1, S)
                if len(tail):
                    tail.reverse()
                    ans = [firstN, secondN]
                    ans.extend(tail)
                    return ans

        return []

\"\"\"
S = Solution()
s = \"123456579\"
s = \"112358130\"
s = \"0123\"
s = \"011\"
s = \"0123\"
s = \"11235813\"
s = \"1101111\"
s = \"0000\"
print(S.splitIntoFibonacci(s))
\"\"\"


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        for i in range(len(S)):
            x = S[:i+1]
            if x != '0' and x.startswith('0'):
                break
            a = int(x)
            for j in range(i+1, len(S)):
                y = S[i+1:j+1]
                if y != '0' and y.startswith('0'):
                    break
                b = int(y)
                fib = [a, b]
                k = j+1
                while k < len(S):
                    nxt = fib[-1] + fib[-2]
                    nxtS = str(nxt)
                    if nxt <= 2**31 - 1 and S[k:].startswith(nxtS):
                        k += len(nxtS)
                        fib.append(nxt)
                    else:
                        break
                else:
                    if len(fib) >= 3:
                        return fib
        return []

class Solution:
    def splitIntoFibonacci(self, S):
        upper_limit = 2 ** 31 - 1
        def split_fib(s, res):
            if s == \"\"  and len(res) > 2 and int(res[-1]) == int(res[-2]) + int(res[-3]):
                return True
            if len(res) > 2 and int(res[-1]) != int(res[-2]) + int(res[-3]):
                return False
            if int(res[-1]) >= upper_limit:
                return False
            
            for i in range(1, len(s)+1):
                if (i > 1 and s[:i][0] == '0'):
                    continue
                res.append(s[:i])
                if split_fib(s[i:], res):
                    return True
                res.pop()
            return False

        res = []
        for i in range(1, len(S)):
            if S[:i][0] == '0' and i > 1:
                continue
            res.append(S[:i])
            if split_fib(S[i:], res) and int(res[-1]) <= upper_limit:
                return res
            res.pop()
        return []
        

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        if len(S) < 3: return []
        for i in range(1, len(S) - 2):
            first = S[:i]
            for j in range(i, len(S) - 1):
                j += 1
                second = S[i:j]
                split = self.dfs(first, second, S[j:], [first, second])
                if split: return split
                
        return []
    
    def notvalid(self, s):
        if int(s) != 0 and s[0] == 0:
            return True
        if int(s) > 2**31 - 1:
            return True
        return False

    
    def dfs(self, s1, s2, rem, seq):
        if self.notvalid(s1) or self.notvalid(s2):
            return []
        s3 = str(int(s1) + int(s2))
        if self.notvalid(s3): return []
        l = len(s3)
        if rem[:l] == s3:
            seq.append(s3)
            if len(rem) > l:
                return self.dfs(s2, s3, rem[l:], seq)
            else:
                return seq
        return []


class Solution:
    
    def __init__(self):
        self.q = []
        
    def splitIntoFibonacci(self, s: str) -> List[int]:
        self.dfs(s,[],0)
        return self.q
    
    def dfs(self,s,q,i):
        if i == len(s):
            if len(q) >= 3: self.q = q[::]
            return len(q) >= 3
        
        for j in range(i , min(len(s), i + 10 ) ):
            v = int(s[i:j+1])
            b1 = (v< 2 ** 31 -1)
            b2 = v == 0 or (v and s[i] != '0')
            b3 = len(q) < 2 or (q[-1] + q[-2] == v)
            if b1 and b2 and b3 and self.dfs(s,q + [v], j + 1):
                return True
        return False

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        # When the first two numbers are decided,
        # all next numbers are decided too.

        for i in range(1, len(S) - 1):
            # need have at least 1 chracter left for third number
            for j in range(i + 1, len(S)):
                first = to_number(S[:i])
                second = to_number(S[i:j])
                ans = [first, second]
                if is_valid_fibonacci(S, j, first, second, ans):
                    return ans
        return []
        
def to_number(s):
    # print(s)
    num = int(s)
    if s.startswith('0') and num != 0:
        return None
    if num < 0 or num > 2 ** 31 - 1:
        return None
    return num

def is_valid_fibonacci(s, curr_index, first, second, ans):
    if first is None or second is None:
        return False
    if curr_index == len(s):
        return True
    expected = first + second
    len_next_num = len(str(expected))
    end_index = curr_index + len_next_num
    next_num = to_number(s[curr_index: end_index])
    if next_num != expected:
        return False
    ans.append(next_num)
    return is_valid_fibonacci(s, end_index, second, next_num, ans)

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        unvisited = []
        for i1 in range(1, len(S)):
            s1 = S[:i1]
            if s1 != \"0\" and s1.startswith(\"0\"):
                continue
            for i2 in range(i1 + 1, len(S)):
                s2 = S[i1:i2]
                if s2 != \"0\" and s2.startswith(\"0\"):
                    continue
                unvisited.append(([int(s1), int(s2)], i2))
        
        while unvisited:
            sequence, suffix_i = unvisited.pop()

            if suffix_i == len(S):
                return sequence

            next_term = sequence[-2] + sequence[-1]

            if next_term <= (1 << 31) - 1:
                next_term_s = str(next_term)

                new_suffix_i = suffix_i + len(next_term_s)
                # if S[suffix_i:suffix_i + len(next_term_s)] == next_term_s:
                if S[suffix_i:new_suffix_i] == next_term_s:
                    # new_suffix_i = suffix_i + len(next_term_s)
                    unvisited.append((sequence + [next_term], new_suffix_i))


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        unvisited = []
        for i1 in range(1, len(S)):
            s1 = S[:i1]
            if s1 != \"0\" and s1.startswith(\"0\"):
                continue
            for i2 in range(i1 + 1, len(S)):
                s2 = S[i1:i2]
                if s2 != \"0\" and s2.startswith(\"0\"):
                    continue
                unvisited.append(([int(s1), int(s2)], i2))
        
        while unvisited:
            sequence, suffix_i = unvisited.pop()

            if suffix_i == len(S):
                return sequence

            next_term = sequence[-2] + sequence[-1]

            if next_term <= (1 << 31) - 1:
                next_term_s = str(next_term)
                new_suffix_i = suffix_i + len(next_term_s)
                if S[suffix_i:new_suffix_i] == next_term_s:
                    unvisited.append((sequence + [next_term], new_suffix_i))


from math import pow

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        total = len(S)
        if total < 3:
            return []

        if S[0] == '0' and S[1] == '0':
            for item in S:
                if item != '0':
                    return []
            return [0] * len(S)

        if S[0] == \"0\":
            first_index = 0
            for second_index in range(first_index+1, total-1):
                result = [0, int(S[1:second_index+1])]
                if self.do_calc(S, second_index+1, total, result):
                    return result
            return []


        for first_index in range(0, total - 2):
            if S[first_index+1] == \"0\":
                result = [int(S[:first_index+1]), 0]
                if self.do_calc(S, first_index+2, total, result):
                    return result
                continue

            for second_index in range(first_index+1, total-1):
                result = [int(S[:first_index+1]), int(S[first_index+1:second_index+1])]
                if self.do_calc(S, second_index+1, total, result):
                    return result
        return []

    def do_calc(self, S, current_index, total, result):
        if current_index >= total:
            return True

        new_value = (result[-1] + result[-2])
        new_value_str = str(new_value)
        new_value_len = len(new_value_str)
        S_value = S[current_index:current_index+new_value_len]
        if S_value == new_value_str and new_value <= pow(2, 31) -1:
            result.append(new_value)
            return self.do_calc(S, current_index + new_value_len, total, result)
        return False

class Solution:
    def get_values(self, s, idx):
        for i in range(idx, len(s)):
            yield (i, s[idx:i+1])
        
    def splitIntoFibonacci(self, S: str) -> List[int]:
        for i, a in self.get_values(S, 0):
            if a != '0' and a.startswith('0'): break
            for j, b in self.get_values(S, i+1):
                if b != '0' and b.startswith('0'): break
                k = j+1
                out = [a,b]
                while k < len(S):
                    v = int(a) + int(b)
                    str_v = str(v)
                    if v <= 2**31 - 1 and S[k:].startswith(str_v):
                        k = k + len(str_v)
                        a, b  = b, str_v
                        out.append(v)
                    else:
                        break
                if len(out) >= 3:                        
                    if len(''.join(map(str, out))) == len(S):
                         return out
        return [] 
                
            


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        unvisited = []
        for i1 in range(1, len(S)):
            s1 = S[:i1]
            if s1 != \"0\" and s1.startswith(\"0\"):
                continue
            for i2 in range(i1 + 1, len(S)):
                s2 = S[i1:i2]
                if s2 != \"0\" and s2.startswith(\"0\"):
                    continue
                unvisited.append(([int(s1), int(s2)], S[i2:]))
        
        while unvisited:
            sequence, suffix = unvisited.pop()
            
            if not suffix:
                return sequence
            
            next_term = sequence[-2] + sequence[-1]
            
            if next_term <= (1 << 31) - 1:
                next_term_s = str(next_term)

                if suffix.startswith(str(next_term)):
                    new_suffix = suffix[len(next_term_s):]
                    unvisited.append((sequence + [next_term], new_suffix))


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def dfs1(prev, cur, pos):
            if pos == len(S)-1:
                return True
            
            nex = prev + cur
            prev = cur
            cur = nex
            if cur > 2 ** 31 - 1:
                return False
            
            if S[pos+1:pos+1+len(str(nex))] == str(nex):
                if len(S[pos+1:pos+1+len(str(nex))]) != 1 and S[pos+1:pos+1+len(str(nex))][0] == '0':
                    return False
                else:
                    return dfs1(prev, cur, pos+len(str(nex)))
            else:
                return False
        
        def dfs2(res, prev, cur, pos):
            res.append(prev)
            if pos == len(S)-1:
                res.append(cur)
                return
            
            nex = prev + cur
            prev = cur
            cur = nex
            dfs2(res, prev, cur, pos+len(str(nex)))
        
        for i in range(len(S)-1):
            for j in range(i+1, len(S)-1):
                if (len(S[:i+1]) > 1 and S[:i+1][0] == '0') or (len(S[i+1:j+1]) > 1 and S[i+1:j+1][0] == '0'):
                    continue
                if dfs1(int(S[:i+1]), int(S[i+1:j+1]), j):
                    res = []
                    dfs2(res, int(S[:i+1]), int(S[i+1:j+1]), j)
                    return res
        
        return []


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        stack = []
        def solve(index):
            if stack and int(stack[-1]) > 2**31-1:
                return False
            #print(stack, S[index:])
            if index == len(S):
                return len(stack) >= 3
            if len(stack) < 2:
                if S[index] == '0':
                    stack.append('0')
                    if solve(index+1):
                        return True
                    stack.pop()
                    return False
                for i in range(index, len(S)):
                    stack.append(S[index:i+1])
                    if solve(i+1):
                        return True
                    stack.pop()
            elif int(stack[-1]) + int(stack[-2]) > int(S[index:]):
                return False
            else:
                if S[index] == '0':
                    if stack[-1] == '0' and stack[-2] == '0':
                        stack.append('0')
                        if solve(index+1):
                            return True
                        stack.pop()
                    return False
                for i in range(index, len(S)):
                    if int(stack[-1]) + int(stack[-2]) == int(S[index:i+1]):
                        stack.append(S[index:i+1])
                        if solve(i+1):
                            return True
                        stack.pop()
            return False
        solve(0)
        return stack

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        for i in range(n):
            fs = S[:i+1]
            if fs != \"0\" and fs.startswith(\"0\"):
                continue
            for j in range(i+1, n):
                ss = S[i+1:j+1]
                if ss != \"0\" and ss.startswith(\"0\"):
                    break
                a, b = int(fs), int(ss)
                fibs = [a, b]
                k = j + 1
                while k < n:
                    next_s = str(fibs[-1] + fibs[-2])
                    next_val = int(next_s)
                    if next_val < 2**31 and S[k:].startswith(next_s):
                        fibs.append(next_val)
                        k += len(next_s)
                    else:
                        break
                if k == n and len(fibs) >= 3:
                    return fibs
        return []
                

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
#         res = []
#         self.dfs(res, S, [])
#         return res[0] if res else []
    
#     def dfs(self, res, S, path):
#         if len(path) >= 3 and not S:
#             res.append(path[:])
#             return True
        
#         for i in range(1, len(S)+1):
#             if i > 1 and S[0] == '0' or int(S[:i]) > 2**31-1:
#                 return
#             if len(path) <= 1:
#                 path.append(int(S[:i]))
#                 if self.dfs(res, S[i:], path):
#                     return True
#                 path.pop()
#             elif path[-1] + path[-2] == int(S[:i]):
#                 path.append(int(S[:i]))
#                 if self.dfs(res, S[i:], path):
#                     return True
#                 path.pop()
                
        # second try
        res = []
        self.dfs(res, S, 0, [])
        return res[0] if res else []
    
    def dfs(self, res, S, index, path):
        # print(path)
        if index == len(S) and len(path) >= 3:
            res.append(path[:])
            return
        
        for i in range(index+1, len(S)+1):
            if (i > index + 1 and S[index] == '0') or int(S[index:i]) > 2**31 - 1:
                return
            temp_num = int(S[index:i])
            if (len(path) >= 2 and temp_num == path[-1] + path[-2]) or len(path) < 2:
                path.append(temp_num)
                self.dfs(res, S, i, path)
                path.pop()



class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        if len(S) < 2: return []
    
        def dfs(s, path, res):

            if not s:
                if len(path) >= 3:
                    res.append(path)
                    if not res:
                        return 

            for  i in range(len(s)):
                
                if (len(s[:i+1]) > 1 and s[0]==\"0\") or int(s[:i+1]) > 2**31-1:
                    continue 
                    
                if len(path) < 2:
                    dfs(s[i+1:], path + [s[:i+1]], res)
                else:
                    if int(path[-2]) + int(path[-1]) == int(s[:i+1]):
                        dfs(s[i+1:], path +[s[:i+1]], res)
        res = []               
        dfs(S,[], res)
        return res[0] if res else []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def isFib(i, a, b, count):
            if i == len(S):
                return [] if count >= 3 else None
            if a > (1<<31) - 1 or b > (1<<31) - 1 or a + b > (1<<31):
                return None
            if S[i:i+1] == ['0'] and a != 0:
                return False
            j = i + len(str(a))
            if S[j:j+1] == ['0'] and b != 0:
                return False
            if S[i:i+len(str(a+b))] != str(a+b):
                return False
            rest =  isFib(i+ len(str(a+b)), b, a+b, count + 1)
            if rest or rest == []:
                return [a+b] + rest
        
        for len_a in range(1, len(S)):
            for len_b in range(1, len(S)):
                str_a  = S[:len_a]
                str_b  = S[len_a:len_a + len_b]
                a, b = int(str_a), int(str_b)
                if a > (1<<31) - 1 or b > (1<<31) - 1:
                    continue
                if (str_a[0] == '0' and len_a > 1) or (str_b[0] == '0' and len_b > 1):
                    continue
                val = isFib(len_a + len_b, int(S[:len_a]), int(S[len_a:len_a + len_b]), 2 )
                if val: return [int(str_a), int(str_b)] + val
                if S[0] == '0':
                    break
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        N = len(S)
        
        for i, j in itertools.combinations(range(1, N), 2):
            a, b = S[:i], S[i:j]
            if(str(int(a)) != a or str(int(b)) != b or int(a) > 2**31-1 or int(b) > 2**31-1):
                continue
            res = []
            res.append(a)
            while(j < N):
                c = str(int(a)+int(b))
                if(not S.startswith(c, j) or int(c) > 2**31-1):
                    res = []
                    break
                res.append(b)
                a, b = b, c
                j += len(c)
            res.append(c)
            if(j == N):
                return res
        return []

class Solution:
    def validFib(self, S, n1, n2, i, ret):
        
        if (n1[0] != '0' and len(n1) >= 1) or n1 == '0':
            num1 = int(n1)
        else:
            return False
        if (n2[0] != '0' and len(n2) >= 1) or n2 == '0':
            num2 = int(n2)
        else:
            return False
        
        num3 = num1 + num2
        # if num1 == 123 and num2 == 456:
        #     print(num3, i)
        n3 = str(num3)
        
        j = 0
        while j + i < len(S) and j < len(n3):
            c1 = n3[j]
            c2 = S[j+i]
            if c1 != c2:
                return False
            j += 1
        
        if len(n1) + len(n2) + len(n3) > len(S):
            return False
        
        if i + len(n3) == len(S) and num3 <= 2**31 - 1:
            ret.append(str(num3))
            return True
        
        if self.validFib(S, n2, n3, i+len(n3), ret) and num3 <= 2**31 - 1:
            ret.append(str(num3))
            return True
        
        return False
    
    
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        ret = []
        
        # print(\"01\".isnumeric())
        
        i = 0
        while i < len(S):
            j = 1
            while i + j < len(S):
                n1 = S[ : i+1]
                n2 = S[i+1 : i+j+1]
                # print(n1, n2)
                if self.validFib(S, n1, n2, i+j+1, ret):
                    ret.append(n2)
                    ret.append(n1)
                    return reversed(ret)
                
                j += 1
            i += 1
        
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        N = 2 ** 31 - 1
        
        def dfs(s, path, res):
            if not s and len(path) > 2:
                res.append(path)
                return
            for i in range(len(s)):
                if len(s[:i + 1]) != len(str(int(s[:i + 1]))) or int(s[:i + 1]) > N: continue
                if len(path) < 2: dfs(s[i + 1:], path + [s[:i + 1]], res)
                elif len(path) > 1 and int(s[:i + 1]) == int(path[-1]) + int(path[-2]):
                    dfs(s[i + 1:], path + [s[:i + 1]], res)
        
        res, ans = [], []
        dfs(S, [], res)
        if not res: return []
        for elem in res[0]:
            ans.append(int(elem))
        return ans
            


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        N = 2 ** 31 - 1
        
        def dfs(s, path, res):
            if not s and len(path) > 2:
                res.append(path)
                return
            for i in range(len(s)):
                if len(s[:i + 1]) != len(str(int(s[:i + 1]))) or int(s[:i + 1]) > N: continue
                if len(path) < 2: dfs(s[i + 1:], path + [s[:i + 1]], res)
                elif len(path) > 1 and int(s[:i + 1]) == int(path[-1]) + int(path[-2]):
                    dfs(s[i + 1:], path + [s[:i + 1]], res)
        
        res, ans = [], []
        dfs(S, [], res)
        print(res)
        if not res: return []
        for elem in res[0]:
            ans.append(int(elem))
        return ans
            


class Solution:
    def splitIntoFibonacci(self, S: str):
        self.res = []
        self.dfs(S, [], 0)
        return self.res
    
    def dfs(self, S, temp, count):
        if not S and count >= 3:
            self.res = temp[:]
            return
        for step in range(1, len(S)+1):
            val = S[:step]
            if str(int(val)) == val and 0 <= int(val) <= pow(2, 31) - 1: # 防止前导 0 的出现
                if count < 2:
                    temp.append(int(val))
                    self.dfs(S[step:], temp, count+1)
                    temp.pop()
                elif temp[count-2] + temp[count-1] == int(val):
                    temp.append(int(val))
                    self.dfs(S[step:], temp, count+1)
                    temp.pop()

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        result = []
        # return arry contains list of possible start in form (num1,num2, start of remain)
        def getStarter():
            arr = []
            for i in range(1,len(S)-1):
                for j in range(i+1,len(S)):
                    s1,s2 = S[:i],S[i:j]
                    if (s1[0] == '0' and len(s1)>1) or (s2[0] == '0' and len(s2)>1):
                        continue
                    arr.append((int(s1),int(s2),j))
            return arr

        def dfs(arr, start):
            if start == len(S) and len(arr) >=3:
                result.append(arr)
                return True
            sum = arr[-2] + arr[-1]
            # get next possible target by len of sum
            length = len(str(sum))
            nextNum = int(S[start:start+length])
            if 0 <= sum <= mx and nextNum == sum:
                return dfs(arr+[sum], start+length)
        
        arr = getStarter()
        mx = 2**31-1
        for num1,num2,start in arr:
            if dfs([num1,num2],start):
                return result
        return []

            

            


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        # Time  complexity: O(N^2)
        # Space complexity: O(N)
        L, T, t = len(S), \"\", []
        for i in range(1, L - 2):
            for j in range(1, L - i -1):
                if i > 1 and S[0] == '0' or j > 1 and S[i] == '0':
                    continue
                a, b = int(S[:i]), int(S[i:i+j])
                T, t = S[:i+j], [a, b]
                while len(T) < L:
                    c = a + b
                    T += str(c)
                    t += [c]
                    a, b = b, c
                if len(T) == L and T == S and len(t) > 2 and t[-1] < 2**31 -1:
                    return t

        return []
        

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def getStarter():
            arr = []
            for i in range(1, len(S) - 1):
                for j in range(i + 1, len(S)):
                    s1, s2 = S[:i], S[i:j]
                    if (s1[0] == \"0\" and len(s1) > 1) or (s2[0] == \"0\" and len(s2) > 1): 
                        continue
                    arr.append((int(s1), int(s2), j))
            return arr                 
        def dfs(arr, i):
            if i == len(S):
                return arr
            sm = arr[-2] + arr[-1]
            l = len(str(sm))
            new = int(S[i:i + l])
            return new == sm and 0 <= sm <= mx and dfs(arr + [new], i + l)
        q, mx = getStarter(), 2 ** 31 - 1
        for p1, p2, i in q:
            seq = dfs([p1, p2], i)
            if seq:
                return seq
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = []
        limit = 2**31 - 1
        def helper(n, prefix):
            nonlocal S, ans
            if n == len(S):
                ans = prefix
                return
            num = sum(prefix[-2:])
            if S[n:].startswith(str(num)) and num <= limit:
                return helper(n + len(str(num)), prefix + [num])
        for i in range(2, min(20, len(S) * 2 // 3 + 1)):
            for j in range(max(1, i-10), min(i, 10)):
                helper(i, [int(S[:j]), int(S[j:i])])
                if ans: break
            if ans: break
        return ans

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        L, T, t = len(S), \"\", []
        for i in range(1,L-2):
        \tfor j in range(1,L-i-1):
        \t\tif (i > 1 and S[0] == '0') or (j > 1 and S[i] == '0'): continue
        \t\ta, b = int(S[:i]), int(S[i:i+j])
        \t\tT, t = S[:i+j], [a,b]
        \t\twhile len(T) < L:
        \t\t\tc = a + b
        \t\t\tT += str(c)
        \t\t\tt += [c]
        \t\t\ta, b = b, c
        \t\tif len(T) == L and T == S and len(t) > 2 and t[-1] < 2**31 - 1: return t
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def getfirst():
            pairs = []
            for i in range(1, len(S)-2):
                for j in range(i+1, len(S)-1):
                    pairs.append((i, j))
            return pairs
                    
        def helper(s, e):
            ans = [S[:s], S[s:e]]
            newS = S[e:]
            while newS:
                nex = int(ans[-1]) + int(ans[-2])
                nex = str(nex)
                if int(nex) >= 2**31:
                    return
                # if nex != '0' and nex[0] == '0':
                #     return 
                if newS[:len(nex)] == nex:
                    newS = newS[len(nex):]
                    ans += nex,
                else:
                    return
            return ans
        
        pairs = getfirst()
        for s, e in pairs:
            ans = helper(s, e)
            if ans:
                return ans
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        for i, l in enumerate(S): 
            
            if str(int(S[:i+1])) == S[:i+1]:
                
                for j in range(i+1, len(S)-1): 
                    
                    if str(int(S[i+1:j+1])) == S[i+1:j+1]: 
                        
                        pre, cur = int(S[:i+1]), int(S[i+1:j+1])
                        res = [pre, cur]
                        
                        start = j+1 
                        while start < len(S):
                            nxt = str(pre+cur)
                            length = len(nxt)
                            if pre + cur <= 2**31 -1  and S.startswith(nxt, start):
                                
                                pre, cur = cur, int(S[start: start+length])
                                res += cur,
                                start += length
                            
                            else:
                                break 
                        else:
                            return res
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        for i in range(len(S)):
            for j in range(len(S)):
                arr=[]
                if(S[0:i+1][0]=='0' and len(S[0:i+1])>=2):
                    break
                arr.append(int(S[0:i+1]))
                if(S[i+1:i+j+1]!=''):
                    arr.append(int(S[i+1:i+j+1]))
                flag=0
                k=i+j+1
                while(k < len(S)):
                    if(len(arr) > 1):
                        val=arr[-1]+arr[-2]
                        if(k+len(str(val)) > len(S) or str(val)!=S[k:k+len(str(val))]):
                            flag=1
                            break
                        else:
                            k+=len(str(val))
                            arr.append(val)
                    else:
                        flag=1
                        break
                if(flag==0):
                    if(len(arr)>2):
                        for i in arr:
                            if(i<0 or i>2**31-1):
                                return []
                        return arr
        if(len(arr)<=2):
            return []
        return arr
                        
                        
                
                    
                    


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        for i in range(len(S)):
            for j in range(len(S)):
                arr=[]
                if(S[0:i+1][0]=='0' and len(S[0:i+1])>=2):
                    continue
                arr.append(int(S[0:i+1]))
                if(S[i+1:i+j+1]!=''):
                    arr.append(int(S[i+1:i+j+1]))
                flag=0
                k=i+j+1
                while(k < len(S)):
                    if(len(arr) > 1):
                        val=arr[-1]+arr[-2]
                        if(k+len(str(val)) > len(S) or str(val)!=S[k:k+len(str(val))]):
                            flag=1
                            break
                        else:
                            k+=len(str(val))
                            arr.append(val)
                    else:
                        flag=1
                        break
                if(flag==0):
                    if(len(arr)>2):
                        for i in arr:
                            if(i<0 or i>2**31-1):
                                return []
                        return arr
        if(len(arr)<=2):
            return []
        return arr
                        
                        
                
                    
                    


#
# @lc app=leetcode id=842 lang=python3
#
# [842] Split Array into Fibonacci Sequence
#
# https://leetcode.com/problems/split-array-into-fibonacci-sequence/description/
#
# algorithms
# Medium (35.93%)
# Likes:    481
# Dislikes: 168
# Total Accepted:    20.5K
# Total Submissions: 56.4K
# Testcase Example:  '\"123456579\"'
#
# 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 splitIntoFibonacci(self, S):
        \"\"\"
        :ref: https://leetcode.com/problems/split-array-into-fibonacci-sequence/discuss/143035/Same-Problem-as-306-Python-simple-and-short-DFS-solution
        \"\"\"
        def getStarter():
            arr = []
            for i in range(1, len(S) - 1):
                for j in range(i + 1, len(S)):
                    s1, s2 = S[:i], S[i:j]
                    if (s1[0] == \"0\" and len(s1) > 1) or (s2[0] == \"0\" and len(s2) > 1): 
                        continue
                    arr.append((int(s1), int(s2), j))
            return arr                 
        def dfs(arr, i):
            if i == len(S):
                return arr
            sm = arr[-2] + arr[-1]
            l = len(str(sm))
            new = int(S[i:i + l])
            return new == sm and 0 <= sm <= mx and dfs(arr + [new], i + l)
        q, mx = getStarter(), 2 ** 31 - 1
        for p1, p2, i in q:
            seq = dfs([p1, p2], i)
            if seq:
                return seq
        return []


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def split(N,s):
            if not s: 
                return N

            c = sum(N[-2:])
            if s.startswith(str(c)):
                return split(N + [c], s[len(str(c)):])

        for i in range(1,len(S)):
            for j in range(i+1, len(S)):
                a = int(S[:i])
                b = int(S[i:j])
                if str(a) == S[:i] and str(b) == S[i:j]:
                    ans = split([a, b], S[j:])
                    if ans and all(x<=2**31-1 for x in ans):
                        return ans
                
        return []

class Solution:
    def splitIntoFibonacci(self, s: str) -> List[int]:
        def isTrue(a,b,s):
            if len(str(a)+str(b)+s) != self.n:return []
            l = [a,b]
            while True:
                c = str(a + b)
                if int(c) > 2147483647:return []
                l.append(int(c))
                if c == s[:len(c)]:
                    a = b;b = int(c)
                    s = s[len(c):]
                    if s == '':return l
                else:return []
        self.n = len(s)
        for i in range(1,len(s)):
            for j in range(i):
                l = isTrue(int(s[0:j+1]),int(s[j+1:i+1]),s[i+1:])
                if l:return l
        return []


class Solution:
    def splitIntoFibonacci(self, s: str) -> List[int]:
        def isTrue(a,b,s):
            if len(str(a)+str(b)+s) != self.n:return []
            l = [a,b]
            while True:
                c = str(a + b)
                if int(c) > 2147483647:return []
                l.append(int(c))
                if c == s[:len(c)]:
                    a = b;b = int(c)
                    s = s[len(c):]
                    if s == '':return l
                else:return []
        self.n = len(s)
        for i in range(1,len(s)):
            for j in range(i):
                l = isTrue(int(s[0:j+1]),int(s[j+1:i+1]),s[i+1:])
                if l:return l
        return []

class Solution:
    def get_num(self, S, i, j, cache):
        if i == j:
            return int(S[i])
        key = '{}-{}'.format(i, j)
        if key in cache:
            return cache[key]
        v = int(S[i:j+1])
        cache[key] = v
        return v
    
    def check(self, st, v):
        if v > 2**31-1:
            return False
        if len(st) < 2:
            return True
        return st[-2] + st[-1] == v
    
    def get_st_key(self, st):
        k1 = None
        k2 = None
        ln = len(st)
        if ln == 0:
            pass
        elif ln == 1:
            k1 = st[-1]
        else:
            k1 = st[-1]
            k2 = st[-2]
            if k1 > k2:
                k1, k2 = k2, k1
        return '{}-{}'.format(k1, k2)
    
    def split(self, S, i, st, res, cache, cache_res):
        # print(i, st, res)
        ln = len(S)
        if i >= ln:
            if len(st) >= 3:
                res[0] = list(st)
                return True
            return False
        key = self.get_st_key(st)
        if key in cache_res:
            return cache_res[key]
        res_local = False
        if S[i] == '0':
            new_v = 0
            if self.check(st, new_v):
                st.append(new_v)
                res_local = self.split(S, i+1, st, res, cache, cache_res)
                del st[-1]
        else:
            for j in range(i, len(S)):
                new_v = self.get_num(S, i, j, cache)
                if self.check(st, new_v):
                    st.append(new_v)
                    res_local = self.split(S, j+1, st, res, cache, cache_res)
                    del st[-1]
                    if res_local:
                        break
                if len(st) >= 2 and new_v > st[-2] + st[-1]:
                    break
        cache_res[key] = res_local
        return res_local
            
    
    def solve(self, S):
        res = [None]
        self.split(S, 0, [], res, {}, {})
        if res[0] is None:
            return []
        # st = res[0]
        # for i in range(2, len(st)):
        #     if st[i-2] + st[i-1] != st[i]:
        #         print('aha!')
        # ln = 0
        # for num in st:
        #     ln += len(str(num))
        # if ln != len(S):
        #     print('wrong len!')
        return res[0]
    
    def splitIntoFibonacci(self, S: str) -> List[int]:
        return self.solve(S)

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        if len(S) < 3: return []
        for i in range(1, len(S) - 2):
            first = S[:i]
            for j in range(i, len(S) - 1):
                j += 1
                second = S[i:j]
                split = self.dfs(first, second, S[j:], [first, second])
                if split: return split
                
        return []
    
    def notvalid(self, s):
        if int(s) != 0 and s[0] == 0:
            return True
        if int(s) > 2**31 - 1:
            return True
        return False

    
    def dfs(self, s1, s2, rem, seq):
        s3 = str(int(s1) + int(s2))
        if self.notvalid(s3): return []
        l = len(s3)
        if rem[:l] == s3:
            seq.append(s3)
            if len(rem) > l:
                return self.dfs(s2, s3, rem[l:], seq)
            else:
                return seq
        return []


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        res = []
        max_len = len(S) // 3 + 1
            
        def add_fibonacci(x, left):
            # print(x)
            # print(left)
            temp1 = x[0]
            temp2 = x[1]
            res = None
            res_left = left
            for i in range(len(left)):
                temp3 = int(left[:i + 1])
                if temp3 == temp1 + temp2 and temp3 < 2 ** 31 - 1:
                    # print(temp3)
                    res = temp3
                    res_left = res_left[i + 1:]
                    break
                elif temp3 > temp1 + temp2:
                    break
            # print(res, res_left)
            return res, res_left
            
        for i in range(1, max_len + 1):
            c1 = S[0:i]
            if len(c1) > 1 and c1[0] == '0':
                break
            for j in range(i + 1, max_len + i + 1):
                c2 =S[i:j]
                if len(c2) > 1 and c2[0] == '0':
                    break
                # next_length = max(len(c1), len(c2))
                next_index = j
                left = S[next_index:]
                res.append(int(c1))
                res.append(int(c2))
                while len(left) > 0:
                    # print(res)
                    # print(res[-2:])
                    temp, left = add_fibonacci(res[-2:], left)
                    if temp is None:
                        res.clear()
                        break
                    res.append(temp)
                #     print(res, left, len(left))
                # print(res)
                if len(res) > 0:
                    break
                res.clear()
            if len(res) > 0:
                break
            
            res.clear()
        return res

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        for i, l in enumerate(S): 
            
            if str(int(S[:i+1])) == S[:i+1]:
                
                for j in range(i+1, len(S)-1): 
                    
                    if str(int(S[i+1:j+1])) == S[i+1:j+1]: 
                        
                        pre, cur = int(S[:i+1]), int(S[i+1:j+1])
                        res = [pre, cur]
                        
                        start = j+1 
                        while S.startswith(str(pre + cur), start):
                            length = len(str(pre+cur)) 
                            pre, cur = cur, int(S[start: start+length])
                            res += cur,
                            start += length 
            
                            if start >= len(S): 
                                return res
                            
                            if pre + cur >= 2**31:
                                break 
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
               
        for i, j in itertools.combinations(range(1, n), 2):
            res = []
            a, b = S[:i], S[i:j]
            #if b != str(int(b)):
            if a != str(int(a)) or b != str(int(b)):
                continue
            res.append(int(a))
            res.append(int(b))
            while j < n:
                c = str(int(a) + int(b))
                if not S.startswith(c, j):
                    break
                res.append(int(c))
                j += len(c)
                a, b = b, c
            if j == n:
                for item in res:
                    if item > 2**31 -1:
                        return []
                return res
        return []

class Solution:
    def splitIntoFibonacci(self, S):
        def getStarter():
            arr = []
            for i in range(1, len(S) - 1):
                for j in range(i + 1, len(S)):
                    s1, s2 = S[:i], S[i:j]
                    if (s1[0] == \"0\" and len(s1) > 1) or (s2[0] == \"0\" and len(s2) > 1): 
                        continue
                    arr.append((int(s1), int(s2), j))
            return arr                 
        def dfs(arr, i):
            if i == len(S):
                return arr
            sm = arr[-2] + arr[-1]
            l = len(str(sm))
            new = int(S[i:i + l])
            return new == sm and 0 <= sm <= mx and dfs(arr + [new], i + l)
        q, mx = getStarter(), 2 ** 31 - 1
        for p1, p2, i in q:
            seq = dfs([p1, p2], i)
            if seq:
                return seq
        return []

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        
        S_len = len(S)
        res = []
        prev = None
        
        def check(index, prev_back, prev):
            if index == S_len:
                return ['#']
            
            buffer = \"\"
            
            for i in range(index, S_len, 1):
                
                if S[index] == '0' and i - index > 0:
                    break
                
                buffer += S[i]
                buffer_int = int(buffer)
                
                if buffer_int > 2**31 - 1:
                    break
                
                if buffer_int == prev_back + prev:
                    x = check(i + 1, prev, buffer_int)
                    if x:
                        return [buffer_int] + x
                    
                elif buffer_int > prev_back + prev:
                    break
                    
            return []
        
        for i in range(0, S_len - 2, 1):
            
            if S[0] == '0' and i + 1 > 1:
                break
            
            for j in range(i+1, S_len - 1, 1):
                
                if S[i+1] == '0' and j - i > 1:
                    break
                
                prev_back = int(S[:i + 1])
                prev = int(S[i+1 : j+1])
                
                x = check(j + 1, prev_back, prev)
                if x:
                    return [prev_back, prev] + x[:-1]
                
            
        return []
                

#
# @lc app=leetcode id=842 lang=python3
#
# [842] Split Array into Fibonacci Sequence
#
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        size = len(S)
        if size < 3: return []
        INT_MAX = (1 << 31) - 1
        def dfs(start, expect, prev, res):
            if start >= size: return len(res) >= 3
            for end in range(start, size):
                number = S[start:end+1]
                if len(number) > 1 and number[0] == '0': break
                num = int(number)
                if num > INT_MAX: break
                if num == expect:
                    res.append(num)
                    if dfs(end + 1, expect + prev, expect, res):
                        return True
                    else:
                        res.pop()
                        break
                elif num > expect: break
            return False
        for end in range(1, size):
            for mid in range(end):
                if S[0] == '0' and mid != 0: continue
                if S[mid+1] == '0' and end != mid + 1: continue
                first = int(S[:mid+1])
                second = int(S[mid+1:end+1])
                res = [first, second]
                if dfs(end + 1, second + first, second, res):
                    return res
        return []



class Solution:
    def splitIntoFibonacci(self, s: str) -> List[int]:
        result = []
        n = len(s)
        
        self.backtrack(s, 0, n, [], result)
        
        return result
    
    def backtrack(self, s, left, n, currArr, result):        
        if len(currArr) > 2:
            if currArr[-1] != currArr[-2] + currArr[-3]:
                return False
            else:
                if left >= n:
                    result.append(currArr)
                    return True
        
        for i in range(left, n):
            
            if (s[left] == \"0\" and i != left) or int(s[left:i+1]) > (2**31)-1:
                return False
                
            newArr = currArr.copy()
            newArr.append(int(s[left:i+1]))
            
            if (len(newArr) > 2):
                if (newArr[-1] != newArr[-2] + newArr[-3]):
                    continue
            
            res = self.backtrack(s, i+1, n, newArr, result)
            
            if res == True:
                return True
            

class Solution:
    def splitIntoFibonacci(self, S: str):    
        max_len = len(S)
        for first_size in range(1, max_len-1):
            for second_size in range(1, max_len-1-first_size):
                res = self.test(S, first_size, second_size)
                if len(res) >= 3 and int(res[-1]) <  2 ** 31 - 1:
                    return res
        return []
        
    def test(self, s, first_size, second_size):
        cursor = 0
        fibo = []
        
        first_number = int(s[:first_size])
        if first_size != len(str(first_number)):
            return []
        
        fibo.append(str(first_number))
        cursor += first_size
        
        second_number = int(s[cursor:cursor+second_size])
        fibo.append(str(second_number))
        cursor += second_size
        
        while cursor <= len(s)-1:
            possible_next = first_number + second_number
            len_next = len(str(possible_next))
            
            next_number = int(s[cursor:cursor+len_next])
            
            if cursor+len_next > len(s):
                return []
            elif not next_number == possible_next:
                return []
            
            fibo.append(str(next_number))
            
            first_number, second_number = second_number, next_number
            cursor += len_next 
                
        return fibo

class Solution:
    def splitIntoFibonacci(self, s: str) -> List[int]:
        
        def dfs(start, string, sequence):
            if start==len(string):
                if len(sequence)>2:
                    return sequence
                return None
            
            num = 0
            for i in range(start, len(string)):
                if i!=start and string[start] == '0':
                    return None
                num  = num*10 + ord(string[i]) - ord('0')
                if num>=2**31:
                    break
                if len(sequence)>1 and sequence[-1] + sequence[-2] != num:
                    continue
                    
                sequence.append(num)
                seq = dfs(i+1, string, sequence)
                if seq != None:
                    return seq
                sequence.pop()   
        
        
        
        for  sticks in range(2, len(s)):
            seq = dfs(0, s, [])
            if seq:
                return seq
        return []

class Solution:
    def __init__(self):
        self.res = []
    
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def helper(pos, temp):
            if pos == len(S): 
                if len(temp) > 2:
                    self.res = temp[:]
                return 
            if S[pos] == '0':
                if len(temp) > 1:
                    if temp[-1] + temp[-2] != 0:
                        return
                temp.append(0)
                helper(pos + 1, temp)
                temp.pop()
            else:
                for i in range(pos + 1, len(S) + 1):
                    curr = int(S[pos : i])
                    if len(temp) < 2:
                        temp.append(curr)
                        helper(i, temp)
                        temp.pop()
                    else:
                        if curr > temp[-1] + temp[-2] or curr > 2 ** 31 - 1:
                            return
                        if curr == temp[-1] + temp[-2]:
                            temp.append(curr)
                            helper(i, temp)
                            temp.pop()
        helper(0, [])
        return self.res