<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>

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isAdditiveNumber(string s) {
        int n = s.length();
        // Try all possible lengths for the first and second number
        for (int i = 1; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                string num1 = s.substr(0, i);
                string num2 = s.substr(i, j - i);
                if (isValid(num1, num2) && checkSequence(s, num1, num2)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    // Check if the number does not have leading zeros unless it's '0'
    bool isValid(const string& num1, const string& num2) {
        return !(num1.length() > 1 && num1[0] == '0') &&
               !(num2.length() > 1 && num2[0] == '0');
    }

    // Check if the remaining part of the string can form a valid additive sequence
    bool checkSequence(const string& s, string num1, string num2) { // Changed to pass by value
        string sum;
        int pos = num1.length() + num2.length();
        while (pos < s.length()) {
            // Calculate the next number in the sequence
            sum = add(num1, num2);
            // Check if the remaining part of the string starts with the calculated sum
            if (s.substr(pos, sum.length()) != sum) {
                return false;
            }
            pos += sum.length();
            num1 = num2;
            num2 = sum;
        }
        return pos == s.length(); // Ensure we've used up the entire string
    }

    // Function to add two numbers represented as strings
    string add(const string& num1, const string& num2) {
        string result;
        int carry = 0;
        int i = num1.length() - 1, j = num2.length() - 1;
        while (i >= 0 || j >= 0 || carry) {
            int x = (i >= 0) ? num1[i--] - '0' : 0;
            int y = (j >= 0) ? num2[j--] - '0' : 0;
            int sum = x + y + carry;
            result.push_back(sum % 10 + '0');
            carry = sum / 10;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

8200