<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 flag=0;
    int n;
    long long prev1, prev2;
    string prevs1, prevs2;
    
    int digits(long long x){
        int cnt=0;
        if(x==0){return 1;}
        while(x){
            x/=10;
            cnt++;
        }
        return cnt;
    }

    void rec(int l, string& temp){
        if(flag){return;}
        if(temp[0]=='0' && stoll(temp)!=0){return;}

        // cout<<"prev1="<<prev1<<" prev2="<<prev2<<endl;
        if(l==n){
            
            flag = 1;
            return;
        }

        int stlen = max(digits(prev1), digits(prev2));
        
        for(int i=0; i<2; i++){
            if(stlen+i > temp.size())continue;

            long long tnum = stoll(temp.substr(0, stlen+i));
            // cout<<"tnum="<<tnum<<" n="<<n<<" temp="<<temp<<endl;

            if( tnum==(prev1+prev2)){
                // string temp2 = temp;
                temp = temp.substr(stlen+i);
                prev1 = prev2;
                prev2 = tnum;
                rec(l+stlen+i, temp);
                // temp = temp2;
            }

        }

    }

    bool isAdditiveNumber(string num) {
        n = num.length();
        for(int i=0;i<(n-1)/2;i++){
            for(int j=i+1;max(i+1, j-i)<=(n-j-1); j++){
                prev1 = stoll(num.substr(0, i+1));
                prev2 = stoll(num.substr(i+1, j-i));

                // cout<<"prevs1="<<prevs1<<" prevs2="<<prevs2<<endl;

                if(digits(prev1)!=(i+1)){continue;}
                if(digits(prev2)!=(j-i)){continue;}
                string temp = num.substr(j+1);
                rec(j+1, temp);
            }
        }
        if(flag==0){
            return false;
        }else{
            return true;
        }
    }
};

// class Solution {
// public:
//         bool isAdditiveNumber(string num) {
//             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;
//             string sum=add(num1, num2);
//             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 add(string n, string m){
//             long long  n1 = stoll(n);
//             long long m1 = stoll(m);
//             long long res1 = n1 + m1;
//             string res = to_string(res1);
//             return res;
//         }
//     };
8800