842.-split-array-into-fibonacci-sequence.md

842. Split Array into Fibonacci Sequence

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


    def dfs(self, idx, S, path):
        ## return True or False

        if idx == len(S):
            return len(path) >= 3
        cur = 0
        for i in range(idx, len(S)):
            ## 在 idx 为 0️⃣ 然后还有后面就可以break了
            
            if i > idx and S[idx] == "0": break

            cur = cur * 10 + int(S[i]) 
            if cur > 2 << 31 - 1: break

            if len(path) < 2 or path[-2] + path[-1] == cur:
                path.append(cur)
                if self.dfs(i + 1, S,path): return True
                path.pop()

            elif len(path) > 2 and path[-2] + path[-1] < cur:
                break
        return False