题目描述
这是 LeetCode 上的「306. 累加数」，难度为「中等」。
Tag : 「回溯算法」、「高精度」
累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
说明：累加序列里的数 不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1：
代码语言：javascript复制输入："112358"
输出：true
解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 1 = 2, 1 2 = 3, 2 3 = 5, 3 5 = 8
示例 2：
代码语言：javascript复制输入："199100199"
输出：true
解释：累加序列为: 1, 99, 100, 199。1 99 = 100, 99 100 = 199
提示：
num仅由数字（0-9）组成
进阶：你计划如何处理由过大的整数输入导致的溢出?
回溯 高精度加法
给定的
的长度只有
，且要求序列的第三个数开始由前两个数相加而来。
容易想到通过 DFS 爆搜每个数的分割点，同时利用累加数的特性（第三个数起，每个数均由为前两数之和）进行剪枝。
具体的，我们可以实现一个 boolean dfs(int u) 函数，入参为当前决策到
的哪一位，返回值为决策结果（序列）是否为累加数序列，爆搜过程中的分割数序列存放到
中。
由于是 从位置
作为开始位置决策如何分割出当前数
，我们可以枚举当前数的结束位置，范围为
，但需要注意分割数不能包含前导零，即如果
，则当前数只能为
。
同时，一个合法的分割数必然满足「其值大小为前两数之和」，因此当前数
能够被添加到
的充要条件为：
长度不足
，即
为序列中的前两数，不存在值大小的约束问题，
可以被直接到
并继续爆搜；
长度大于等于
，即
需要满足「其值大小为前两数之和」要求，以此条件作为剪枝，满足要求的
才能追加到
中并继续爆搜。
最后，在整个 DFS 过程中我们需要监测「当前数」与「前两数之和」是否相等，而分割数长度最大为
，存在溢出风险，我们需要实现「高精度加法」，实现一个 check 函数，用于检查 a b 是否为 c，其中 a、b 和 c 均为使用「逆序」存储数值的数组（最高位对应个位，举个
