### 描述

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.

For example:

`"112358"` is an additive number because 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

`"199100199"` is also an additive number, the additive sequence is: `1, 99, 100, 199`.

1 + 99 = 100, 99 + 100 = 199

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

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

How would you handle overflow for very large input integers?

### 分析

### 代码

{% if book.java %}
```java
// 多入口深搜
// 时间复杂度O(n^3)，空间复杂度O(1)
public class Solution {
for (int i = 1; i <= num.length() / 2; ++i) {
if (num.charAt(0) == '0' && i > 1) continue;
for (int j = i + 1; j < num.length(); ++j) {
if (num.charAt(i) == '0' && j - i > 1) continue;
if (dfs(num, 0, i, j)) return true;
}
}
return false;
}

// 判断从 [i, j) 和 [j, k) 出发,能否走到尽头
private static boolean dfs(String num, int i, int j, int k) {
long num1 = Long.parseLong(num.substring(i, j));
long num2 = Long.parseLong(num.substring(j, k));
final String addition = String.valueOf(num1 + num2);