难度: Medium
累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
说明：累加序列里的数，除数字 0 之外，不会 以 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
提示：
1 <= num.length <= 35num 仅由数字（0 - 9）组成进阶：你计划如何处理由过大的整数输入导致的溢出?
运行时间: 19 ms
内存: 16.1 MB
from collections import deque
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
length = len(num)
if length < 3: return False
max_length = length // 2
num_list = []
def my_check(a,b,string):
c = a+b
c_string = str(a+b)
if not string.startswith(c_string):
return False
else:
c_len = len(c_string)
if c_len == len(string): return True
else:
return my_check(b, c, string[c_len:])
if num[:2] == '00':
return my_check(0,0,num[2:])
if num[0] == '0':
for j in range(1, length//2):
b = int(num[1:j+1])
return my_check(0, b, num[j+1:])
for i in range(0, length//2):
a = int(num[:i+1])
if num[i+1] == '0':
if my_check(a, 0, num[i+2:]):
return True
else:
for j in range(i+1, length):
b = int(num[i+1:j+1])
if my_check(a, b, num[j+1:]):
return True
return False
# for i in range(1, length//2 + 1):
# a = int(num[:i])
# for j in range(i+1, length+1):
# b = int(num[i:j])
# c = str(a+b)
# if not num[j+1].startswith():
# def get_new_nums(num):
# n_digits = len(num)
# possible_num = []
# if num[0] == '0':
# a == 0
# if (n_digits - 1) % 2 == 1: return []
# j = 1 + (n_digits - 1) // 2
# if num[1:j] == num[j+1:]
# for i in range(n_digits//2):
# a = int(num[:i+1])
# if num[i+1] == '0':
# b == 0
# c = int(num[i+2:])
# if a == c:
# possible_num.append()
# else:
# a = int(num[:i+1])
# for j in range(i+1, n_digits-1):
# if n_digits - j < max(j, j-i):
# break
# if num[j+1] == '0':
# pass
# else:
# b = int(num[i+1:j+1])
# c = int(num[j+1:])
# if a + b == c:
# possible_num.append(num[i+1:])
# return possible_num
# to_check = deque()
# to_check.append(num)
# while len(to_check) > 0:
# cur_num = to_check.popleft()
# new_nums = get_new_nums(cur_num)
# if len(new_nums) > 0:
# return True
# for i in range(1, length+1):
# new_nums = get_new_nums(cur_num[:i])
# if len(new_nums) > 0:
# for nn in new_nums:
# to_check.append(nn+cur_num[i:])
# return False
# # to_check = deque()
# # to_check.append(num)
# # while True:
# # cur_num = to_check.popleft()
# # new_nums = get_new_nums(cur_num)
# # if len(new_nums) > 1:
# # return True
# # for i in range(length):
# def valid_3_nums(num):
# if
# for i in range(length // 2):
这个题解的思路是暴力搜索所有可能的累加数组合。具体来说： 1. 首先判断字符串长度是否小于3，如果是就直接返回False，因为累加序列至少要有3个数。 2. 然后用两个循环来枚举前两个数a和b。第一个数a的范围是[0,length//2]，第二个数b的范围是[i+1,length]，其中i是a的结束位置。 3. 在枚举a和b时，如果a或b以0开头且不是0本身，就跳过。 4. 对于每一对a和b，调用辅助函数my_check来检查以a和b开头能否形成有效的累加序列。 5. my_check函数递归地计算a+b，将结果与原字符串的剩余部分比较，如果吻合就继续递归检查b和a+b，否则返回False。 6. 如果找到任何一个有效的a和b组合，就返回True，否则在所有组合都检查完后返回False。
时间复杂度: O(n^4)
空间复杂度: O(n)
```python
from collections import deque
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
length = len(num)
if length < 3: return False
max_length = length // 2
num_list = []
def my_check(a, b, string):
'''
递归检查以a和b开头的累加序列能否与字符串string匹配
a: 第一个数
b: 第二个数
string: 待匹配的字符串
'''
c = a + b
c_string = str(a + b)
if not string.startswith(c_string):
return False
else:
c_len = len(c_string)
if c_len == len(string): return True
else:
return my_check(b, c, string[c_len:])
if num[:2] == '00':
return my_check(0, 0, num[2:])
if num[0] == '0':
for j in range(1, length//2):
b = int(num[1:j+1])
return my_check(0, b, num[j+1:])
for i in range(0, length//2):
a = int(num[:i+1])
if num[i+1] == '0':
if my_check(a, 0, num[i+2:]):
return True
else:
for j in range(i+1, length):
b = int(num[i+1:j+1])
if my_check(a, b, num[j+1:]):
return True
return False
```
在累加数问题中，第一个数a的最大长度取length//2是基于累加数序列的性质和长度考虑的。因为累加数至少包含三个数，第三个数是前两个数的和，且第三个数的长度至少与前两个数中较长者相等。假设第一个数a取超过length//2的长度，那么剩余的字符串长度将不足以容纳第二个数b和至少与a等长的第三个数，从而无法形成有效的累加序列。因此，这个范围不会导致错过有效的累加数序列。
在大多数数字表示法中，除了数字0本身，以0开头的数字被视为非法或多余的前导0。因此，在处理累加数时，如果一个数以0开头并且长度超过1，通常应跳过这样的数。这种处理是为了防止如'01'或'003'等解释为有效数字的情况。在累加数的上下文中，这种处理是正确的，因为每个数字都应当是一个没有前导零的整数。因此，这种处理不会漏掉符合条件的累加数。
my_check函数通过递归检查累加序列的正确性。它首先计算两个数a和b的和，然后将这个和转换成字符串，并检查当前字符串是否以这个和的字符串形式开始。如果是，递归进入下一个级别，以b和这个和作为新的a和b继续匹配字符串的剩余部分。这种方法理论上能够确保正确匹配字符串的每一个部分。然而，如果实现中存在逻辑错误，如基本情况和终止条件处理不当，或者数值运算中的问题，可能会导致错误的匹配结果。
如果输入字符串的长度特别长，递归深度的确可能导致性能问题或者栈溢出，因为每一层递归都会消耗一定的栈空间和处理时间。为了避免递归过深，可以考虑使用迭代代替递归，或者使用尾调用优化（尽管Python本身不支持尾调用优化）。另一种方法是使用动态规划或其他非递归的算法框架，这样可以避免深层递归带来的问题。