306.Additive Number

Tags: [brute_force], [recursion]

Link: https://leetcode.com/problems/additive-number/#/description

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should containat leastthree numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
"112358"is an additive number because the digits can form an additive sequence:1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199"

is also an additive number, the additive sequence is:

1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note:Numbers in the additive sequence cannot have leading zeros, so sequence1, 2, 03or1, 02, 3is invalid.

Given a string containing only digits'0'-'9', write a function to determine if it's an additive number.

Follow up:
How would you handle overflow for very large input integers?

Solution: Brute Force

class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        if not num or len(num) < 3:
            return False

        for i in xrange(len(num) - 2):
            for j in xrange(i + 1, len(num) - 1):
                # Check leading 0 for prev_1, if prev_1 = 0 that's fine, 
                # but if prev_1's length > 1 and there exists leading 0, we can return False directly.
                if num[0] == '0' and i - 0 + 1 > 1:
                    return False

                prev_1 = int(num[:i + 1])

                # Check leading 0 for prev_2, if prev_2 = 0 that's fine,
                # but if prev_2's length > 1 and there exists leading 0, we can skip it, until i changed.
                if num[i + 1] == '0' and j - (i + 1) + 1 > 1:
                    continue

                prev_2 = int(num[i + 1: j + 1])

                if self.is_additive_num_helper(num, j + 1, prev_1, prev_2):
                    return True

        return False

    def is_additive_num_helper(self, num, index, prev_1, prev_2):
        # base case.
        if index >= len(num):
            return True

        for i in xrange(index, len(num)):
            if num[index] == '0' and i - index + 1 > 1:
                return False

            curr = int(num[index: i + 1])
            if curr == prev_1 + prev_2 and self.is_additive_num_helper(num, i + 1, prev_2, curr):
                return True

        return False

Revelation:

• Each number, try all possible positions to cut, to build the current number.
• The cases we should be careful, such as num = "000", num = "0123".

Note:

• Time complexity = O(n!), n is the length of the given num. Because first level of recursion we have k options, second recursion level we have k - 1 options, the third recursion we have k - 2 options... 1 <= k < n, because before the recursion we two level loops to generate all possible prev_1 and prev_2.