306.累加数

累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
说明： 累加序列里的数 不会 以 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 <= 35
• num 仅由数字（ 0 - 9 ）组成
  进阶： 你计划如何处理由过大的整数输入导致的溢出?

解法一：暴力穷举

这里的前提是需要先把 415.字符串相加 理解。

需要注意的点是：有效值不能是以 ‘0’ 开头的。

func isAdditiveNumber(num string) bool {
    n := len(num)
    for i := 0; i < n-1; i++ {
        for j := i + 1; j < n; j++ {
            if dfs(num, i, j) {
                return true
            }
        }
    }
    return false
}

func dfs(num string, first, second int) bool {
    n, last := len(num), 0
    for second < n {
        if (num[last] == '0' && first > last+1) || (num[first] == '0' && second > first+1) {
            return false
        }
        s := addStrings(num[last:first], num[first:second])
        if second+len(s) > n || num[second:second+len(s)] != s {
            return false
        }
        last, first, second = first, second, second+len(s)
    }
    return true
}

func addStrings(num1 string, num2 string) string {
    flag := 0
    n1 := len(num1) - 1
    n2 := len(num2) - 1
    var res string
    for n2 >= 0 || n1 >= 0 || flag != 0 {
        tmp := 0
        if n1 >= 0 {
            tmp += int(num1[n1] - '0')
            n1--
        }
        if n2 >= 0 {
            tmp += int(num2[n2] - '0')
            n2--
        }
        tmp += flag
        if tmp >= 10 {
            tmp %= 10
            flag = 1
        } else {
            flag = 0
        }
        res = strconv.Itoa(tmp) + res
    }
    return res
}