306. 累加数

class Solution:

    def isAdditiveNumber(self, num: str) -> bool:
        for s2 in range(len(num)):
            for s1 in range(s2):
                prev, cur, remain = num[:s1], num[s1: s2], num[s2:]
                if len(prev) > 0 and self.without_prefix_zero(prev) \
                        and len(cur) > 0 and self.without_prefix_zero(cur) \
                        and len(remain) > 0 and self.without_prefix_zero(remain) \
                        and self.check(int(prev), int(cur), remain):
                    return True
        return False

    def check(self, prev: int, cur: int, remain: str):
        if len(remain) == 0:
            return True

        for s3 in range(len(remain) + 1):
            post = remain[:s3]
            if len(post) > 0 and self.without_prefix_zero(post) \
                    and int(post) == prev + cur and self.without_prefix_zero(remain[s3:]):
                return self.check(cur, int(post), remain[s3:])

        return False

    @staticmethod
    def without_prefix_zero(s: str):
        return len(s) == 1 or not s.startswith('0')