# Question

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

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

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

Example 1:

Input: "112358"
Output: true
Explanation: 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


Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199


How would you handle overflow for very large input integers?

# Solution

class Solution(object):
"""
:type num: str
:rtype: bool
"""
if len(num) <= 2:
return False
return self.backtracking(num, None, None)

def backtracking(self, remaining, prev1, prev2):
if prev1 is not None and prev2 is not None:
if len(remaining) == 0:
return True
if remaining[0] == '0':
if prev1 + prev2 != 0:
return False
else:
return self.backtracking(remaining[1:], prev2, 0)

max_remaining = int(remaining)
if max_remaining == prev1 + prev2:
return True
elif max_remaining < prev1 + prev2:
return False
else:
digits = 0
while max_remaining > prev1 + prev2:
max_remaining //= 10
digits += 1
if max_remaining == prev1 + prev2:
return self.backtracking(remaining[-digits:], prev2, max_remaining)
return False

# Populate the 1st number
elif prev1 is None:
if remaining[0] == '0':
return self.backtracking(remaining[1:], 0, None)

# The length must be shorter or equal to half of the string length
for i in range(1, len(remaining) // 2 + 1):
if self.backtracking(remaining[i:], int(remaining[:i]), None):
return True
return False

# Populate the 2nd number
else:
if remaining[0] == '0':
return self.backtracking(remaining[1:], prev1, 0)

# The length of the remaining number must be larger or equal to the 1st number
for i in range(1, len(remaining) - len(str(prev1)) + 1):
if self.backtracking(remaining[i:], prev1, int(remaining[:i])):
return True
return False