Split Array into Fibonacci Sequence

Intuition

Solution

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

        for i in range(1, len(S)):
            for j in range(i + 1, len(S)):
                x = S[:i]
                y = S[i:j]
                if int(x) > 2147483648 or int(y) > 2147483648:
                    break
                tmp = [x, y]
                if x[0] == '0' and x != '0':
                    continue
                elif y[0] == '0' and y != '0':
                    continue
                index = j
                while S[index:].startswith(str(int(x) + int(y))):
                    x, y = y, str(int(x) + int(y))
                    if int(y) > 2147483648:
                        break
                    index += len(y)
                    tmp.append(y)
                if index == len(S):
                    return [int(m) for m in tmp]
        return []