<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 func(string& s,long long a,long long b,long long c,int ind){
        // if(a>900000000000000000||b>900000000000000000||c>900000000000000000){
        //     return false;
        // }
        long long n=pow(10,ceil(s.length()/2.0));
        if(a>n||b>n||c>n){
            return false;
        }
        if(ind==s.length()){
            if(a+b==c&&a!=-1&&b!=-1&&c!=-1){
                return true;
            }
            return false;
        }
        bool x=false;
        if(a==-1){
            x=x||func(s,s[ind]-'0',b,c,ind+1);
            return x;
        }
        if(b==-1){
            if(a!=0){
                x=x||func(s,a*10+s[ind]-'0',b,c,ind+1);
            }
            x=x||func(s,a,s[ind]-'0',c,ind+1);
            return x;
        }
        if(c==-1){
            if(b!=0){
                x=x||func(s,a,b*10+s[ind]-'0',c,ind+1);
            }
            x=x||func(s,a,b,s[ind]-'0',ind+1);
            return x;
        }
        if(a+b==c){
            if(s[ind]!=0){
                x=x||func(s,b,c,s[ind]-'0',ind+1);   
            }
            else{
                if(c!=0){
                    x=x||func(s,b,c*10,0,ind+1);
                }
            }
        }
        else{
            if(c!=0){
                x=x||func(s,a,b,c*10+s[ind]-'0',ind+1);
            }
        }
        return x;
    }
    bool isAdditiveNumber(string s) {
        return func(s,-1,-1,-1,0);
    }
};
7700