Additive Number

A much more efficient approach is to realize that an additive sequence is uniquely determined by its first two numbers. We can iterate through all possible first and second numbers, and for each pair, check if they can form a valid additive sequence that consumes the entire input string.

• 1. The main function isAdditiveNumber iterates through all possible lengths, i and j, for the first two numbers.
• 2. The loop for i (length of the first number) runs from 1 to n/2.
• 3. The loop for j (length of the second number) runs from 1 up to the point where the remaining string length n-i-j is at least max(i, j).
• 4. Inside the loops, extract the first two number strings, s1 and s2.
• 5. Check for invalid leading zeros. If s1 has a leading zero (and length > 1), we can break the outer loop. If s2 has one, continue to the next j.
• 6. Call a recursive helper function, checkSequence(s1, s2, rest_of_string), to validate the remainder of the string.
• 7. The checkSequence function is the core of the backtracking:
  • a. Base Case: If the remaining string is empty, it means the whole string was consumed by a valid sequence, so return true.
  • b. Calculate the sum of the two previous numbers using a stringAdd helper.
  • c. Check if the remaining string starts with the calculated sum string. If not, return false.
  • d. If it does, make a recursive call with the next set of numbers: checkSequence(s2, sum, rest.substring(sum.length())).
• 8. If checkSequence returns true at any point, the main function returns true.
• 9. If the loops complete without finding a solution, return false.

We use two nested loops to select the first two numbers, num1 and num2. The outer loop determines the length of num1, and the inner loop determines the length of num2. Some optimizations can be applied to the loop bounds. For instance, the length of the first or second number cannot be more than half the total string length, because the third number must be at least as long as the longer of the first two.

After selecting num1 and num2, we start a validation process. This process recursively or iteratively generates the next number in the sequence (sum = num1 + num2) and checks if the remaining input string starts with this sum. If it does, we continue the process with num2 and sum. If at any point the check fails, or if we successfully consume the entire string, the process terminates.

Since the numbers can be very large (up to 35 digits), we cannot use standard integer types like long. Instead, we must represent numbers as strings and implement a string addition helper function to handle the 'Follow up' part of the problem.

class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        if (n < 3) return false;

        // i is the length of the first number
        for (int i = 1; i <= n / 2; ++i) {
            // j is the length of the second number
            // The third number's length must be >= max(i, j).
            // So, n - i - j >= max(i, j).
            for (int j = 1; Math.max(i, j) <= n - i - j; ++j) {
                if (isValid(i, j, num)) {
                    return true;
                }
            }
        }
        return false;
    }

    // Checks if a valid sequence can be formed starting with numbers of length i and j
    private boolean isValid(int i, int j, String num) {
        String s1 = num.substring(0, i);
        String s2 = num.substring(i, i + j);

        // Rule: no leading zeros, unless the number is "0" itself.
        if (s1.length() > 1 && s1.charAt(0) == '0') return false;
        if (s2.length() > 1 && s2.charAt(0) == '0') return false;

        String rest = num.substring(i + j);
        return checkSequence(s1, s2, rest);
    }

    // Recursively checks if the 'rest' of the string follows the additive sequence
    private boolean checkSequence(String prev1, String prev2, String rest) {
        if (rest.isEmpty()) {
            return true; // The entire string has been consumed by the sequence
        }

        String sum = stringAdd(prev1, prev2);
        if (!rest.startsWith(sum)) {
            return false; // The next number in the string doesn't match the sum
        }

        // Recurse with the next pair of numbers
        return checkSequence(prev2, sum, rest.substring(sum.length()));
    }

    // Helper function to add two numbers represented as strings
    private String stringAdd(String n1, String n2) {
        StringBuilder res = new StringBuilder();
        int i = n1.length() - 1;
        int j = n2.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0 || carry != 0) {
            int digit1 = i >= 0 ? n1.charAt(i--) - '0' : 0;
            int digit2 = j >= 0 ? n2.charAt(j--) - '0' : 0;
            int sum = digit1 + digit2 + carry;
            res.append(sum % 10);
            carry = sum / 10;
        }
        return res.reverse().toString();
    }
}