Easy to understand python solution


  • 0
    R

    This is a backtracking problem and reminds me of NO. 91 decode ways. The difference is at current stage, we need the last number (n2) and the second to last number (n1), add them up and compare the total to an upcoming number (n3).

    If n3 is found, we do the recursion and set newN1 = n2, newN2 = current number

    class Solution(object):
        
        def helper(self, num, n1, n2, count):
            if len(num) == 0:
                if count >= 3:
                    return True
                return False
                
            t = n1 + n2
            for i in xrange(1, len(num)+1):
                s3 = num[:i]
                if len(s3) > 1 and s3[0] == "0":
                    return False
                
                n3 = int(s3)                
                if t == n3 and self.helper(num[i:], n2, n3, count+1):
                    return True
            return False
        
        
        def isAdditiveNumber(self, num):
            """
            :type num: str
            :rtype: bool
            """
            for i in xrange(1, len(num)+1):
                for j in xrange(i+1, len(num)+1):
                    s1 = num[:i]
                    if len(s1) > 1 and s1[0] == "0":
                        continue
                    s2 = num[i:j]
                    if len(s2) > 1 and s2[0] == "0":
                        continue
                    count = 2
                    if self.helper(num[j:], int(s1), int(s2), count):
                        return True
            
            return False

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.