题目描述：
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.
Follow up:
How would you handle overflow for very large input integers?
题目大意：
累加数是指其各位数字可以组成累加序列的正数。
一个有效的累加序列应该包含至少3个数字。除前两个数以外，序列中剩下的数字都应该迭代地等于前面两个数的和（类似于斐波那契数列）。
例如：
"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
注意：累加序列中的数字不应包含前导零，因而序列1, 2, 03或者1, 02, 3都是无效的。
给定一个字符串代表一个整数，编写函数判断其是否是累加数。
进一步思考：
对于特别大的整数，怎样处理溢出问题？
解题思路：
关于进一步思考，Python原生支持大数运算，不需要考虑溢出问题。Java可以使用BigInteger。
解法I 迭代法：
枚举前两个数，然后循环判断剩余的数是否满足累加序列。
使用itertools.combinations可以生成前两个数起始位置的组合。
参考：https://leetcode.com/discuss/70089/python-solution
Python代码：
class Solution(object):
def isAdditiveNumber(self, num):
"""
: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
解法II 递归法：
Python代码：
class Solution(object):
def isAdditiveNumber(self, num):
"""
: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
本文链接：http://bookshadow.com/weblog/2015/11/18/leetcode-additive-number/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
