# 0ms concise C++ solution (perfectly handles the follow-up and leading 0s)

• use a helper function to add two strings.

Choose first two number then recursively check.

Note that the length of first two numbers can't be longer than half of the initial string, so the two loops in the first function will end when i>num.size()/2 and j>(num.size()-i)/2, this will actually save a lot of time.

Update the case of heading 0s
e.g. "100010" should return false

``````class Solution {
public:
for(int i=1; i<=num.size()/2; i++){
for(int j=1; j<=(num.size()-i)/2; j++){
if(check(num.substr(0,i), num.substr(i,j), num.substr(i+j))) return true;
}
}
return false;
}
bool check(string num1, string num2, string num){
if(num1.size()>1 && num1[0]=='0' || num2.size()>1 && num2[0]=='0') return false;
if(num==sum) return true;
if(num.size()<=sum.size() || sum.compare(num.substr(0,sum.size()))!=0) return false;
else return check(num2, sum, num.substr(sum.size()));
}
string res;
int i=n.size()-1, j=m.size()-1, carry=0;
while(i>=0 || j>=0){
int sum=carry+(i>=0 ? (n[i--]-'0') : 0) + (j>=0?  (m[j--]-'0') : 0);
res.push_back(sum%10+'0');
carry=sum/10;
}
if(carry) res.push_back(carry+'0');
reverse(res.begin(), res.end());
return res;
}
};``````

• Implement string addition is a boost!

• ``````bool isAdditiveNumber(string num) {
if(num.length()<3)
return false;
int step=0;
//防止越界
long front=0,second=0;
for(int i=0;i<num.length()-1;){
front=front*10+num[i]-'0';
int j=i+1;
second=0;
for(;j<num.length();){
if(j==i+1&&num[j]=='0'){
second=0;
return true;
else
break;
}else{
second=second*10+num[j]-'0';
return true;
++j;
}
}
++i;
}
return false;
}

bool isAdditiveHelper(string num,int step,long front,long second,int depth){
if(depth==0&&step==num.length()-1)
return false;
else if(depth>0&&step==num.length()-1){
return true;
}
string temp=num.substr(step+1,num.length()-step-1);
long result_should=front+second;
long res_get=0;
int i=0;
for(;i<temp.length();){
if(i==0&&temp[i]=='0'){
return false;
}
res_get=res_get*10+temp[i]-'0';
if(res_get>result_should)
return false;
else if(res_get==result_should){
}
++i;
}
return false;
}
``````

• In the last line of `check`, you can simply write

``````return check(num2, sum, num.substr(sum.size()));
``````

• You are right. Thanks for advise!

• The test data is too weak.when I input the "100010",I get the answer "1".Obviously,the output should be "0"

• Why the output of `100010` is `0` (`false`)? It is `1` (`true`): `10 + 0 + 0 = 10`.

• Each subsequent number in the sequence must be the sum of the preceding two,while "10 + 0 + 0" contains three numbers. According to the code above, the answer is "10 + 00 = 10"

• Oh, I mistaken the problem. But I try the above code on `100010` and the output is actually `false`. Have you made sure you rewrite the code perfectly correctly?

• Great idea, but how did you handle the leading zero constraint?

• You are right. I have not handled the '00' case. Thanks for pointing out.

• A small change on your code to handle the leading zero case:

``````for(int len1 = 1; len1 <= num.size() / 2; ++len1)
{
string s1 = num.substr(0, len1);
if(s1[0] == '0' && len1 > 1) break;
for(int len2 = 1; len2 <= (num.size() - len1) / 2; ++len2)
{
string s2 = num.substr(len1, len2);
if(s2[0] == '0' && len2 > 1) break;
if(helper(s1, s2, num.substr(len1 + len2)))
return true;
}
}``````

• Thanks. I already updated the code.~

• You code would fail for the test case: 101.

``````if(num1.size()>0 && num1[0]=='0' || num2.size()>0 && num2[0]=='0') return false;
``````

should be

``if(num1.size()>1 && num1[0]=='0' || num2.size()>1 && num2[0]=='0') return false;``

• Just a typo. Thanks for pointing out~

• Great solution! I learn a lot from your solution. And nice implementation of string add.

• : ) Glad you say that, bro

• I think this line needs update:
if(num.size()<=sum.size() || sum.compare(num.substr(0,sum.size()))!=0) return false;

should be:
if(num.size()<sum.size()

• Java solution based on your code.

``````private String add(String a, String b) {
StringBuilder rst = new StringBuilder();
int i = a.length() - 1, j = b.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry + (i >= 0 ? a.charAt(i--) - '0' : 0) + (j >= 0 ? b.charAt(j--) - '0' : 0);
rst.insert(0, sum % 10);
carry = sum / 10;
}
return rst.toString();
}

private boolean check(String a, String b, String c) {
if (a.length() > 1 && a.charAt(0) == '0' || b.length() > 1 && b.charAt(0) == '0') return false;
if (sum.equals(c)) return true;
if (c.length() <= sum.length() || !c.substring(0, sum.length()).equals(sum)) return false;
return check(b, sum, c.substring(sum.length()));
}

for (int i = 1; i <= (num.length() >> 1); i++) {
for (int j = 1; j <= ((num.length() - i) >> 1); j++) {
if (check(num.substring(0, i), num.substring(i, i + j), num.substring(i + j))) return true;
}
}
return false;
}``````

• ``````string add(string n, string m) {
string res = to_string(atoll(n.c_str()) + atoll(m.c_str()));
return res;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.