## Description

An additive number is a string whose digits can form an additive sequence.

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, return true if it is an additive number or false otherwise.

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

Constraints:

• 1 <= num.length <= 35
• num consists only of digits.

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

## Solutions

Let the first digit start with one digit, and the second digit will be searched for higher digits. The first two digits are confirmed, and the third digit is obtained by adding them.

The three arrays are arranged to form a string, which is the same length as the original string if it is less than the original length, then take out the second and third numbers from the previous calculation, and use the same method to get the third number, then add the current string, and then sum Compared to the original string length.

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

Handling very large input integers that exceed the maximum value representable by native data types (e.g., int or long in Python) requires a strategy to avoid overflow. Here’s an approach to handle such cases:

### Handling Overflow

To manage very large integers that could potentially cause overflow, you can perform arithmetic operations as string manipulations. This means converting the numerical addition operation into a character-by-character addition, similar to how you would manually add numbers on paper. This approach eliminates the risk of overflow by not relying on the numerical limits of the data types.

### Implementation Strategy

1. String Addition Function: Implement a function to add two large numbers represented as strings. This function should handle carrying over digits for sums greater than 9 and return the sum as a string.

2. Modified Additive Check: Use the string addition function within the logic that checks if the given number is an additive sequence. Iterate through possible first and second numbers, represented as substrings, and use the addition function to generate each subsequent number. Compare the generated number with the next part of the main string to see if the sequence continues correctly.

3. Edge Cases: Ensure the initial two numbers do not start with a zero unless they are actually zero, as per the problem’s definition of an additive sequence. Also, handle cases where the generated sequence correctly ends at the end of the main string.

• class Solution {
int n = num.length();
for (int i = 1; i < Math.min(n - 1, 19); ++i) {
for (int j = i + 1; j < Math.min(n, i + 19); ++j) {
if (i > 1 && num.charAt(0) == '0') {
break;
}
if (j - i > 1 && num.charAt(i) == '0') {
continue;
}
long a = Long.parseLong(num.substring(0, i));
long b = Long.parseLong(num.substring(i, j));
if (dfs(a, b, num.substring(j))) {
return true;
}
}
}
return false;
}

private boolean dfs(long a, long b, String num) {
if ("".equals(num)) {
return true;
}
if (a + b > 0 && num.charAt(0) == '0') {
return false;
}
for (int i = 1; i < Math.min(num.length() + 1, 19); ++i) {
if (a + b == Long.parseLong(num.substring(0, i))) {
if (dfs(b, a + b, num.substring(i))) {
return true;
}
}
}
return false;
}
}

• class Solution {
public:
int n = num.size();
for (int i = 1; i < min(n - 1, 19); ++i) {
for (int j = i + 1; j < min(n, i + 19); ++j) {
if (i > 1 && num[0] == '0') break;
if (j - i > 1 && num[i] == '0') continue;
auto a = stoll(num.substr(0, i));
auto b = stoll(num.substr(i, j - i));
if (dfs(a, b, num.substr(j, n - j))) return true;
}
}
return false;
}

bool dfs(long long a, long long b, string num) {
if (num == "") return true;
if (a + b > 0 && num[0] == '0') return false;
for (int i = 1; i < min((int) num.size() + 1, 19); ++i)
if (a + b == stoll(num.substr(0, i)))
if (dfs(b, a + b, num.substr(i, num.size() - i)))
return true;
return false;
}
};

• class Solution:
def isAdditiveNumber(self, num: str) -> bool:

def dfs(startIndex: int, out: List[int]) -> bool:
# equal check is here
if len(out) >= 3 and out[-1] != out[-2] + out[-3]:
return False
if startIndex == len(num):
return len(out) >= 3

for i in range(startIndex, len(num)):
current = num[startIndex: i + 1]
if (len(current) > 1 and current[0] == '0'):
break

out.append(int(current))
if dfs(i + 1, out):
return True
out.pop()

return False

if not num:
return False
return dfs(0, [])

#############

# follow up: super large number, solve overflow issue
class Solution:
def addStrings(num1: str, num2: str) -> str:
carry = 0
result = []

i, j = len(num1) - 1, len(num2) - 1
while i >= 0 or j >= 0 or carry:
x = int(num1[i]) if i >= 0 else 0
y = int(num2[j]) if j >= 0 else 0
sum = x + y + carry
result.append(str(sum % 10))
carry = sum // 10
i, j = i - 1, j - 1

return ''.join(reversed(result))

n = len(num)
for i in range(1, n):
for j in range(i+1, n):
num1, num2 = num[:i], num[i:j]
if (len(num1) > 1 and num1[0] == '0') or (len(num2) > 1 and num2[0] == '0'):
continue
while j < n:
if not num.startswith(sum, j):
break
j += len(sum)
num1, num2 = num2, sum
if j == n:
return True
return False

#############

class Solution:
def isAdditiveNumber(self, num: str) -> bool:
def dfs(a, b, num):
if not num:
return True
if a + b > 0 and num[0] == '0':
return False
for i in range(1, len(num) + 1):
if a + b == int(num[:i]):
if dfs(b, a + b, num[i:]):
return True
return False

n = len(num)
for i in range(1, n - 1): # 1st cut
if i > 1 and num[0] == '0': # 0 + 1 = 1 is fine, but 00 + 1 is wrong
break
for j in range(i + 1, n): # 2nd cut, so making it a 3-segments
if j - i > 1 and num[i] == '0':
break
if dfs(int(num[:i]), int(num[i:j]), num[j:]): # better than below, early stop
return True
return False

• func isAdditiveNumber(num string) bool {
n := len(num)
var dfs func(a, b int64, num string) bool
dfs = func(a, b int64, num string) bool {
if num == "" {
return true
}
if a+b > 0 && num[0] == '0' {
return false
}
for i := 1; i < min(len(num)+1, 19); i++ {
c, _ := strconv.ParseInt(num[:i], 10, 64)
if a+b == c {
if dfs(b, c, num[i:]) {
return true
}
}
}
return false
}
for i := 1; i < min(n-1, 19); i++ {
for j := i + 1; j < min(n, i+19); j++ {
if i > 1 && num[0] == '0' {
break
}
if j-i > 1 && num[i] == '0' {
continue
}
a, _ := strconv.ParseInt(num[:i], 10, 64)
b, _ := strconv.ParseInt(num[i:j], 10, 64)
if dfs(a, b, num[j:]) {
return true
}
}
}
return false
}