<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 ans = 0;
    unsigned long long int find(string s)
    {
        unsigned long long int t = 0;
        if(s[0] == '0' && s.length() > 1) return -1;
        for(auto i : s)
        t = t * 10 + (i - '0');

        return t;
    }
    void f(int i,int n,string num,unsigned long long int k,unsigned long long int s,unsigned long long int prev)
    {
        if(i >= n)
        {
            if(k <= 2) return;
            else
            ans = true;
        }
        string t = "";
        //bool ans = false;
        for(int j=i;j<n;j++)
        {
            //if(num[j] == '0') return false;
            t += num[j];
            unsigned long long int v = find(t);
            if(v == -1) return;
            if(k < 2 || v == s)
            {
                cout<<v<<" "<<s<<endl;
                f(j+1,n,num,k+1,prev + v,v);
            }
        }

        //return ans;
    }
    bool isAdditiveNumber(string num) {
        unsigned long long int s = 0,k = 0,prev = 0;
        int i = 0;
        if(num.length() < 3) return 0;
        while(i < num.length() && num[i] == '0') i++;
        if(i >= num.length() && num.length() >= 3) return 1;
       
        f(0,num.length(),num,k,s,prev);
        return ans;
    }
};
10200