## 题目描述：

Additive number is a positive integer whose digits can form additive sequence.

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.

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 sequence `1, 2, 03` or `1, 02, 3` is invalid.

Given a string represents an integer, write a function to determine if it's an additive number.

How would you handle overflow for very large input integers?

## 题目大意：

`"112358"`是一个累加数，因为其数位可以形成这样的累加序列： `1, 1, 2, 3, 5, 8`.

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

`"199100199"`也是一个累加数，因为累加序列是`1, 99, 100, 199`.

`1 + 99 = 100, 99 + 100 = 199`

## Python代码：

``````class Solution(object):
"""
:type num: str
:rtype: bool
"""
n = len(num)
for i, j in itertools.combinations(range(1, n), 2):
a, b = num[:i], num[i:j]
if a != str(int(a)) or b != str(int(b)):
continue
while j < n:
c = str(int(a) + int(b))
if not num.startswith(c, j):
break
j += len(c)
a, b = b, c
if j == n:
return True
return False
``````

## Python代码：

``````class Solution(object):
"""
:type num: str
:rtype: bool
"""
def isValid(num):
return len(num) == 1 or num[0] != '0'

def search(a, b, c):
d = str(int(a) + int(b))
if not isValid(d) or not c.startswith(d):
return False
if c == d:
return True
return search(b, d, c[len(d):])

size = len(num)
for x in range(1, size / 2 + 1):
for y in range(x + 1, size):
a, b, c = num[:x], num[x:y], num[y:]
if not isValid(a) or not isValid(b):
continue
if search(a, b, c):
return True
return False
``````

Pingbacks已关闭。