题解 | #累加序列#

dfs，记录每三个数最后一个等于前两个的和,不符合或长度大于1且第一位为0剪枝

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr string字符串 
# @return bool布尔型
#
class Solution:
    def AdditiveArray(self , arr: str) -> bool:
        # write code here
        def dfs(arr, t):
            if not arr and len(t) >= 3 and t[-1] == t[-2] +  t[-3]:
                return True
            for i in range(len(arr)):
                c = arr[:i + 1]
                if len(c) > 1 and c[0] == "0":
                    continue
                c = int(c)
                if len(t) < 2 or t[-2] + t[-1] == c:
                    if dfs(arr[i + 1:], t + [c]):
                        return True
            return False
        return dfs(arr, [])