<p>An <strong>additive number</strong> is a string whose digits can form an <strong>additive sequence</strong>.</p>

<p>A valid <strong>additive sequence</strong> should contain <strong>at least</strong> three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.</p>

<p>Given a string containing only digits, return <code>true</code> if it is an <strong>additive number</strong> or <code>false</code> otherwise.</p>

<p><strong>Note:</strong> Numbers in the additive sequence <strong>cannot</strong> have leading zeros, so sequence <code>1, 2, 03</code> or <code>1, 02, 3</code> is invalid.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> &quot;112358&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> 
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
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> &quot;199100199&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> 
The additive sequence is: 1, 99, 100, 199.&nbsp;
1 + 99 = 100, 99 + 100 = 199
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 35</code></li>
	<li><code>num</code> consists only of digits.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> How would you handle overflow for very large input integers?</p>

class Solution {
public:
bool solve(string nums1,string nums2,int i,string s)
{
    if(i>=s.size())
    return true;

    string sum;
    int m=nums1.size(),n=nums2.size(),j=m-1,k=n-1,carry=0,add,digit,len=s.size();
    while(j>=0||k>=0)
    {
        add=carry;
        if(j>=0)
        add+=nums1[j--]-'0';
        if(k>=0)
        add+=nums2[k--]-'0';
        carry=add/10;
         digit=add%10;
        sum.push_back(digit+'0');
    }
    if(carry!=0)
    sum.push_back(carry+'0');
    //cout<<sum.size()<<" ";
    //cout<<sum<<" ";
    if(sum.size()>len-i)
    return false;
    reverse(sum.begin(),sum.end());
    cout<<nums1<<" "<<nums2<<" "<<sum<<"* ";
    if(sum!=s.substr(i,sum.size()))
    return false;
    return solve(nums2,sum,i+sum.size(),s);


}
    bool isAdditiveNumber(string s) {
        int n=s.size(),i,j;
        if(n<3)
        return false;
        string nums1="",nums2="";
        for(i=0;i<n-2;i++)
        {
            nums1.push_back(s[i]);
            nums2="";
            for(j=i+1;j<n-1;j++)
            {
                nums2.push_back(s[j]);
                if(solve(nums1,nums2,j+1,s))
                return true;
                if(s[i+1]=='0')
                break;
            }
            if(s[0]=='0')
            break;
        }
        return false;

    }
};
8500