Additive Number

Problem: Additive Number

This problem can be solved by search all possible additive splits by depth-first search. We can extract the first number and the second number then sum them up. After that, we check whether the following number equals the sum calculated. If so, we replace the first number by the second and the second by the sum and keep searching.

Code in Python:

class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        def additive(pos, nums):
            for i in xrange(pos+1, len(num)+1):
                if i - pos > 1 and num[pos] == '0':
                    continue
                if not nums:
                    if additive(i, [int(num[pos:i])]):
                        return True
                elif len(nums) == 1:
                    if additive(i, nums + [int(num[pos:i])]):
                        return True
                else:
                    if nums[0] + nums[1] == int(num[pos:i]):
                        if i == len(num):
                            return True
                        if additive(i, [nums[1], int(num[pos:i])]):
                            return True
            return False
        return additive(0, [])

There's also a non-recursive depth-first search solution with 3 loops discussed. Maybe we can make the return earlier if we only extract the first number from left half of the number.