1. Problem Statement

An additive number is a string whose digits can form an additive sequence.
A valid additive sequence is a sequence of numbers where each number (after the first two) is the sum of the previous two.

You are given a string num representing a non-negative integer.
Return true if num is an additive number, otherwise return false.

Example 1:
Input: num = "112358"
Output: true
Explanation: The sequence is [1, 1, 2, 3, 5, 8], where each number is the sum of the previous two.

Example 2:
Input: num = "199100199"
Output: true
Explanation: The sequence is [1, 99, 100, 199].

Example 3:
Input: num = "1023"
Output: false
Explanation: The sequence cannot be additive due to leading zero in “02”.

---

2. Key Insight

We must split the string into at least three parts — first number a, second number b, and the remaining string rest, which should continue the additive sequence.

We try all possible splits for the first and second numbers.
For each pair (a, b), we simulate the addition process and check if the rest of the string follows the pattern.

Important rule:

• Numbers cannot have leading zeros, unless the number itself is "0".

---

3. Example Walkthrough

Let’s take num = "112358".

Try:

• a = “1”, b = “1” → next should be “2”
• Remaining string starts with “2” → matches!
  Continue checking → “3”, “5”, “8” → all valid → return true.

---

4. Approach

Steps:

1. Iterate over all possible splits for the first number a (i index).
2. Iterate over all possible splits for the second number b (j index).
3. For each pair (a, b):
   • Skip if either has a leading zero.
   • Simulate addition: keep computing sum = a + b as a string.
   • Check if the remaining string starts with sum.
     If it does, continue; else break.
4. If we reach the end of the string successfully → return true.
5. If no valid sequence found → return false.

---

5. Java Implementation

public class AdditiveNumber {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();

        for (int i = 1; i <= n / 2; i++) {
            for (int j = i + 1; j < n; j++) {
                String a = num.substring(0, i);
                String b = num.substring(i, j);

                // Skip invalid cases with leading zeros
                if ((a.length() > 1 && a.startsWith("0")) || 
                    (b.length() > 1 && b.startsWith("0"))) {
                    continue;
                }

                if (isValidSequence(a, b, num.substring(j))) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isValidSequence(String a, String b, String remaining) {
        while (!remaining.isEmpty()) {
            String sum = addStrings(a, b);
            if (!remaining.startsWith(sum)) {
                return false;
            }
            remaining = remaining.substring(sum.length());
            a = b;
            b = sum;
        }
        return true;
    }

    private String addStrings(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0, i = a.length() - 1, j = b.length() - 1;

        while (i >= 0 || j >= 0 || carry > 0) {
            int x = (i >= 0) ? a.charAt(i--) - '0' : 0;
            int y = (j >= 0) ? b.charAt(j--) - '0' : 0;
            int sum = x + y + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }

        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        AdditiveNumber obj = new AdditiveNumber();
        System.out.println(obj.isAdditiveNumber("112358"));   // true
        System.out.println(obj.isAdditiveNumber("199100199")); // true
        System.out.println(obj.isAdditiveNumber("1023"));      // false
    }
}

---

6. Complexity Analysis

Operation	Complexity	Explanation
Number of splits	O(n²)	Two nested loops for a and b
String addition per check	O(n)	Each addStrings() is linear
Total	O(n³)	For all possible pairs
Space	O(n)	Due to string operations and recursion depth

Even though this looks high, in practice n ≤ 35 (per LeetCode constraint), so it runs efficiently.

---

7. Common Pitfalls

1. Leading Zeros — Must be rejected unless the number is "0".
   Example: "1023" → invalid because "02" is not allowed.
2. Integer Overflow — Use string-based addition (not integer arithmetic).
3. Substring Boundaries — Be careful when slicing substrings in nested loops.

---

8. Key Takeaways

• This is a backtracking-style simulation problem.
• The solution must use string addition to avoid overflow.
• Early pruning on invalid leading zeros significantly improves performance.