## 题目 #

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.

Given a string containing only digits `'0'-'9'`, write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence `1, 2, 03` or `1, 02, 3` is invalid.

Example 1:

``````Input: "112358"
Output: true
Explanation: 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
``````

Example 2:

``````Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
``````

Follow up:How would you handle overflow for very large input integers?

## 解题思路 #

• 在给出的字符串中判断该字符串是否为斐波那契数列形式的字符串。
• 由于每次判断需要累加 2 个数字，所以在 DFS 遍历的过程中需要维护 2 个数的边界，`firstEnd``secondEnd`，两个数加起来的和数的起始位置是 `secondEnd + 1`。每次在移动 `firstEnd``secondEnd` 的时候，需要判断 `strings.HasPrefix(num[secondEnd + 1:], strconv.Itoa(x1 + x2))`，即后面的字符串中是否以和为开头。
• 如果第一个数字起始数字出现了 0 ，或者第二个数字起始数字出现了 0，都算非法异常情况，都应该直接返回 false。

## 代码 #

``````
package leetcode

import (
"strconv"
"strings"
)

// This function controls various combinations as starting points
if len(num) < 3 {
return false
}
for firstEnd := 0; firstEnd < len(num)/2; firstEnd++ {
if num[0] == '0' && firstEnd > 0 {
break
}
first, _ := strconv.Atoi(num[:firstEnd+1])
for secondEnd := firstEnd + 1; max(firstEnd, secondEnd-firstEnd) <= len(num)-secondEnd; secondEnd++ {
if num[firstEnd+1] == '0' && secondEnd-firstEnd > 1 {
break
}
second, _ := strconv.Atoi(num[firstEnd+1 : secondEnd+1])
if recursiveCheck(num, first, second, secondEnd+1) {
return true
}
}
}
return false
}

//Propagate for rest of the string
func recursiveCheck(num string, x1 int, x2 int, left int) bool {
if left == len(num) {
return true
}
if strings.HasPrefix(num[left:], strconv.Itoa(x1+x2)) {
return recursiveCheck(num, x2, x1+x2, left+len(strconv.Itoa(x1+x2)))
}
return false
}

``````

Apr 8, 2023