842.md

842. Split Array into Fibonacci Sequence

Solution 1 (time O(n), space O(n))

class Solution(object):
    def splitIntoFibonacci(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        n = len(S)
        ans = []

        def backtrack(index):
            if index == n:
                return len(ans) >= 3
            curr = 0
            for i in range(index, n):
                if i > index and S[index] == '0':
                    break
                curr = curr * 10 + ord(S[i]) - ord('0')
                if curr > 2 ** 31 - 1:
                    break
                if len(ans) < 2 or curr == ans[-1] + ans[-2]:
                    ans.append(curr)
                    if backtrack(i + 1):
                        return True
                    ans.pop()
                elif len(ans) > 2 and curr > ans[-1] + ans[-2]:
                    break
            return False

        backtrack(0)
        return ans