题目
难度：★★★☆☆
类型：字符串
方法：回溯法
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例
示例 1:
输入: "112358"
输出: true
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:
输入: "199100199"
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
进阶:
你如何处理一个溢出的过大的整数输入?
解答
我们使用回溯法来解决这个问题。只要确定了前两个数字num1和num2，这种组合状态下能否使整个数字成为累加数已经可以确定了。
我们设置两个位置参数i和j，用来定位这两个数字（两个数字是相接的），num1=num[0:i]，num2=num[i:j]，剩余数字res=num[j:]，循环遍历。
回溯算法的设计。
回溯函数的输入为两个数字和剩余字符，分别用n1，n2和r表示，我们将n1和n2的和记为s，注意数据类型；
是累加数的充要条件是s与r完全相等。
可以断定不是累加数的充要条件是：和s的长度已经大于剩余r长度，或者r不是以s开头的。
其他情况下，需要调用本函数继续回溯，这时的两个输入数字都要改变，n1替换成n2，n2替换成它们的和s，r替换成去掉从中s后的剩余数字。
回溯的思想体现在，每当遇到绝对不可以满足条件的情况，函数直接返回False，进行下一轮循环，避免了多余的计算，这也是回溯法通过剪枝的方式优于暴力求解的重要原因。
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
"""
| n1 | n2 | ....
0 i j
两个分界点，分别用i和j来表示。
:param num:
:return:
"""
if len(num) < 3:
return False
def backtrack(n1, n2, r):
"""
开始回溯。
:param n1: 第一个数字。
:param n2: 第二个数字。
:param r: 剩下的数字。
:return:
"""
s = str(int(n1) + int(n2))
if s == r:
return True
elif len(s) > len(r) or r[:len(s)] != s:
return False
else:
return backtrack(n2, s, r[len(s):])
def is_invalid_num(n):
"""
判断是否为非法数字，以0开头，例如01,065
:param n:
:return:
"""
return len(n) > 1 and n[0] == '0'
for i in range(1, len(num) + 1): # 找到第一个数：num[:i]
for j in range(i + 1, len(num)): # 找到第二个数：num[i:j]
num1, num2, rest = num[:i], num[i:j], num[j:]
if is_invalid_num(num1) or is_invalid_num(num2): # 避免0开头的非0数
continue
if backtrack(num1, num2, rest):
return True
return False
如有疑问或建议，欢迎评论区留言~
