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
``````

How would you handle overflow for very large input integers?

Credits:
Special thanks to @jeantimex for adding this problem and creating all test cases.

``````class Solution {
public:
for (int i = 1; i < num.size(); ++i) {
string s1 = num.substr(0, i);
if (s1.size() > 1 && s1[0] == '0') break;
for (int j = i + 1; j < num.size(); ++j) {
string s2 = num.substr(i, j - i);
long d1 = stol(s1), d2 = stol(s2);
if ((s2.size() > 1 && s2[0] == '0')) break;
long next = d1 + d2;
string nextStr = to_string(next);
if (nextStr != num.substr(j, nextStr.length())) continue; // optimization here
string allStr = s1 + s2 + nextStr;
while (allStr.size() < num.size()) {
d1 = d2;
d2 = next;
next = d1 + d2;
nextStr = to_string(next);
allStr += nextStr;
}
if (allStr == num) return true;
}
}
return false;
}
};
``````

``````class Solution {
public:
bool res = false;
vector<long> out;
helper(num, 0, out, res);
return res;
}
void helper(string& num, int start, vector<long>& out, bool& res) {
if (res) return;
if (start >= num.size()) {
if (out.size() >= 3) res = true;
return;
}
for (int i = start; i < num.size(); ++i) {
string str = num.substr(start, i - start + 1);
if ((str.size() > 1 && str[0] == '0') || str.size() > 19) break;
long curNum = stol(str), n = out.size();
if (out.size() >= 2 && curNum != out[n - 1] + out[n - 2]) continue;
out.push_back(curNum);
helper(num, i + 1, out, res);
out.pop_back();
}
}
};
``````

``````class Solution {
public:
for (int i = 1; i < num.size(); ++i) {
string s1 = num.substr(0, i);
if (s1.size() > 1 && s1[0] == 0) break;
for (int j = i + 1; j < num.size(); ++j){
string s2 = num.substr(i, j - i);
if (s2.size() > 1 && s2[0] == 0) break;
if(helper(num.substr(j), s1, s2)) return true;
}
}
return false;
}
bool helper(string num, string num1, string num2){
if ((num1.size() > 1 && num1[0] == '0') || (num2.size() > 1 && num2[0] == '0')) return false;
string sumStr = to_string(stol(num1) + stol(num2));
if (sumStr == num) return true;
if (sumStr.size() >= num.size() || num.substr(0, sumStr.size()) != sumStr) return false;
return helper(num.substr(sumStr.size()), num2, sumStr);
}
};
``````

``````// Follow up, handle overflow for very large input integers.
class Solution {
public:
for (int i = 1; i < num.size(); ++i) {
string s1 = num.substr(0, i);
if (s1.size() > 1 && s1[0] == 0) break;
for (int j = i + 1; j < num.size(); ++j){
string s2 = num.substr(i, j - i);
if (s2.size() > 1 && s2[0] == 0) break;
if(helper(num.substr(j), s1, s2)) return true;
}
}
return false;
}
bool helper(string num, string num1, string num2){
if ((num1.size() > 1 && num1[0] == '0') || (num2.size() > 1 && num2[0] == '0')) return false;
if (sumStr == num) return true;
if (sumStr.size() >= num.size() || num.substr(0, sumStr.size()) != sumStr) return false;
return helper(num.substr(sumStr.size()), num2, sumStr);
}
string add(string num1, string num2) {
string res;
int i = (int)num1.size() - 1, j = (int)num2.size() - 1, carry = 0;
while (i >= 0 || j >= 0) {
int val1 = (i >= 0) ? (num1[i--] - '0') : 0;
int val2 = (j >= 0) ? (num2[j--] - '0') : 0;
int sum = val1 + val2 + carry;
res.push_back(sum % 10 + '0');
carry = sum / 10;
}
if (carry) res.push_back(carry + '0');
reverse(res.begin(), res.end());
return res;
}
};
``````

Split Array into Fibonacci Sequence