<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:
    string addNums(string& a, string& b) {
        int idx = 0;
        bool carry = false;
        string ans = "";
        while (idx < size(a) || idx < size(b) || carry) {
            int digit = 0;
            if (idx < size(a)) {
                digit += a[size(a) - 1 - idx] - '0';
            }
            if (idx < size(b)) {
                digit += b[size(b) - 1 - idx] - '0';
            }
            if (carry) {
                digit += 1;
            }

            if (digit > 9) {
                digit -= 10;
                carry = true;
            }
            else {
                carry = false;
            }
            ans += to_string(digit);
            idx += 1;
        }
        //cout << "ans before reverse " << ans << endl;
        reverse(ans.begin(), ans.end());
        //cout << "sum of " << a << " " << b << " is " << ans << endl;
        return ans;
    }
    bool helper(string& num, int idx, string& first, string& second, string& third, bool& found) {
        if (idx == size(num) && first != "-1" && second != "-1" && third != "-1") {
            found = true;
            return true;
        }
        else {
            string new_num = "";
            bool zero = false;
            for (int i = idx; i < size(num); i++) {
                new_num += num[i];
                //cout << "new_num " << new_num << " made by slicing " << idx << " to " << i << endl;
                //cout << "int_num " << int_num << " made by slicing from " << idx << " to " << i << endl;
                if (new_num == "0") {
                    zero = true;
                }
                if (first == "-1") {
                    //cout << "no frist number, setting " << new_num << " to first" << endl;
                    first = new_num;
                    if (helper(num, i + 1, first, second, third, found)) {
                        return true;
                    }
                    //cout << "couldn't find sequence with first num " << first << " , resetting to -1" << endl;
                    first = "-1";
                }
                else if (second == "-1") {
                    second = new_num;
                    //cout << "no second number, setting " << new_num << " to second" << endl;
                    if (helper(num, i + 1, first, second, third, found)) {
                        return true;
                    };
                    //cout << "couldn't find sequence with seoncd num " << second << " , resetting to -1" << endl;
                    second = "-1";
                }
                else { //we have more than two nums
                    string summ = addNums(first, second);
                    //cout << "summ of first second " << first << " " << second << " " << summ << endl;
                    if (size(new_num) > size(summ)) { //it's too big -- return
                        //cout << "int_num " << new_num << " too big for first and second " << first << " " << second << endl;
                        return false;
                    }
                    else if (new_num == summ) {
                        //cout << "found sequence with " << first << " " << second << " " << new_num << endl;
                        string temp = first;
                        first = second;
                        second = new_num;
                        third = new_num;
                        if (helper(num, i + 1, first, second, third, found)) {
                            return true;
                        };
                        third = "-1";
                        second = first; //undo the assignment -- go back to original
                        first = temp;
                        //cout << "cound't find sequence with int_num " << new_num << " reset first and secodn to " << first << " " << second << endl;
                    }
                }
                if (zero) {
                    break;
                }
            }
        }
        return false;
    }
    bool isAdditiveNumber(string num) {
        bool found = false;
        string first = "-1";
        string second = "-1";
        string third = "-1";
        helper(num, 0, first, second, third, found);
        return found;
    }
};
10500