<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:
    pair<long, long> findSum(string num, long total, int strIndex) {
        string sum = "";
        for(long i = strIndex; i < num.size(); i++) {
            sum += num[i];
            if (num[strIndex] == '0' && stol(sum) != 0) return {-1, -1};
            if (stol(sum) == total) return {i, stol(sum)};
            if (stol(sum) > total) return {-1, -1};
        }
        return {-1, -1};
    }

    bool checkTail(string num, long first, long second, int index) {
        int fi = first, se = second;
        cout << "initial: " << first << " " << second << " index: " << index << endl;
        pair<long, long> f = findSum(num, first + second, index);
        if (f.first == num.size() - 1) return true;
        while(f.first != -1) {
            fi = se;
            se = f.second;
            // cout << "looped: " << fi << " " << se << " index: " << f.first + 1 << endl;
            f = findSum(num, fi + se, f.first + 1);
            if (f.first == num.size() - 1) return true;
        }
        if (f.first == num.size() - 1) return true;
        return false;
    }

    bool isAdditiveNumber(string num) {
        string veryFirst = "";
        string first = "", second = "";
        for (int l = 0; l < num.size() - l - 1; l++) {
            first += num[l];
            if (first[0] == '0' && l > 0) break;
            second = "";
            for(int s = l+1; s < num.size() - second.size(); s++) {
                // cout<<"index " << s << " " << num.size() << " " <<  (l + 1) << " " << (s + 1) << " " << num.size() - (l + 1) - (s + 1) << endl;
                second += num[s];
                if (second[0] == '0' && stol(second) != 0) break;
                if (checkTail(num, stol(first), stol(second), s+1)) return true;
            }
        }
        return false;
    }
};
9000