Problem Description

The "Additive Number" problem asks you to determine if a given string num is an additive sequence. An additive sequence is a list of numbers where each number (starting from the third) is the sum of the previous two. The sequence must contain at least three numbers, and no number in the sequence can have leading zeros (unless the number itself is 0).

• Input: A string num containing only digits.
• Output: Return true if num can form an additive sequence, otherwise return false.
• Constraints:
  • Each number must not have leading zeros unless it is 0 itself.
  • All digits in num must be used, and numbers must be non-empty.
  • You cannot reuse digits or skip any digit.

Example:
Input: "112358"
Output: true
Explanation: The sequence is 1, 1, 2, 3, 5, 8 (1+1=2, 1+2=3, 2+3=5, 3+5=8).

Thought Process

To solve this problem, we need to check if we can split the string into at least three numbers such that each number (from the third onwards) is the sum of the previous two. The main challenge is that the numbers can be of any length, and we need to try all possible combinations for the first and second numbers.

A brute-force way would be to try every possible split for the first and second numbers, then check if the rest of the string follows the additive property. This can be time-consuming, but since the input size is reasonable, it's feasible with some optimizations.

We must also be careful to avoid numbers with leading zeros, which are not allowed unless the number is exactly '0'. The key is to systematically try all partitions for the first two numbers and check if the rest of the string can be built by repeatedly adding the previous two numbers.

Solution Approach

Let's break down the solution step by step:

1. Try all possible splits for the first and second numbers:
   • For the first number, try every possible substring starting at index 0 and ending before the last two digits (since we need at least three numbers).
   • For the second number, try every possible substring immediately after the first number, but ensure there are enough digits left for at least one more number.
2. Check for leading zeros:
   • If a number has more than one digit and starts with '0', skip this split.
3. Iteratively build the sequence:
   • Starting from the third number, calculate the sum of the previous two numbers.
   • Check if the next part of the string matches this sum.
   • If yes, continue; if not, break and try the next split.
4. Return true if the entire string is used up and the sequence is valid.

We use string slicing and integer conversion to handle large numbers, since the input can be bigger than standard integer ranges (especially in languages like JavaScript or Java).

Example Walkthrough

Let's walk through the example num = "112358":

1. Try first number = "1", second number = "1".
2. Next number should be 1 + 1 = 2. The next part of the string is "2", which matches.
3. Now, previous two numbers are 1 and 2. Next should be 1 + 2 = 3. The next part is "3", which matches.
4. Now, previous two numbers are 2 and 3. Next should be 2 + 3 = 5. The next part is "5", which matches.
5. Now, previous two numbers are 3 and 5. Next should be 3 + 5 = 8. The next part is "8", which matches.
6. All digits are used, and the sequence is valid. Return true.

Time and Space Complexity

Brute-force approach:
- For each possible first number (up to n/2 digits), and for each possible second number (up to n/2 digits), we check the rest of the string.
- For each split, we may traverse the rest of the string linearly.
- So, the time complexity is roughly O(n^2) for trying splits, and for each, up to O(n) for validation, so O(n^3) in the worst case.
- Space complexity is O(1) (not counting recursion stack or string slices), as we only use variables for indices and temporary numbers.

Optimized approach:
- By pruning splits with leading zeros and stopping early if sums don't match, we reduce unnecessary checks.
- Still, the worst-case time complexity remains O(n^3) due to nested loops and validation.

Summary

The Additive Number problem tests your ability to systematically try all possible ways to partition a string into numbers, while respecting constraints like no leading zeros and using all digits. The key insight is to try all valid splits for the first two numbers and check if the rest of the string can be constructed as an additive sequence. By carefully handling edge cases and using string manipulation, the solution remains efficient and clear.

Code Implementation

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        for i in range(1, n):
            for j in range(i+1, n):
                num1, num2 = num[:i], num[i:j]
                # Skip if numbers have leading zeros
                if (len(num1) > 1 and num1[0] == '0') or (len(num2) > 1 and num2[0] == '0'):
                    continue
                x1, x2 = int(num1), int(num2)
                k = j
                while k < n:
                    x3 = x1 + x2
                    x3_str = str(x3)
                    if not num.startswith(x3_str, k):
                        break
                    k += len(x3_str)
                    x1, x2 = x2, x3
                if k == n:
                    return True
        return False
      

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
        for (int i = 1; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                string num1 = num.substr(0, i);
                string num2 = num.substr(i, j-i);
                if ((num1.length() > 1 && num1[0] == '0') || (num2.length() > 1 && num2[0] == '0'))
                    continue;
                long long x1 = stoll(num1), x2 = stoll(num2);
                int k = j;
                while (k < n) {
                    long long x3 = x1 + x2;
                    string x3_str = to_string(x3);
                    if (num.substr(k, x3_str.length()) != x3_str)
                        break;
                    k += x3_str.length();
                    x1 = x2;
                    x2 = x3;
                }
                if (k == n)
                    return true;
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                String num1 = num.substring(0, i);
                String num2 = num.substring(i, j);
                if ((num1.length() > 1 && num1.charAt(0) == '0') || 
                    (num2.length() > 1 && num2.charAt(0) == '0')) {
                    continue;
                }
                long x1 = Long.parseLong(num1), x2 = Long.parseLong(num2);
                int k = j;
                while (k < n) {
                    long x3 = x1 + x2;
                    String x3Str = Long.toString(x3);
                    if (!num.startsWith(x3Str, k)) {
                        break;
                    }
                    k += x3Str.length();
                    x1 = x2;
                    x2 = x3;
                }
                if (k == n) return true;
            }
        }
        return false;
    }
}
      

var isAdditiveNumber = function(num) {
    const n = num.length;
    for (let i = 1; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let num1 = num.slice(0, i);
            let num2 = num.slice(i, j);
            if ((num1.length > 1 && num1[0] === '0') || (num2.length > 1 && num2[0] === '0')) {
                continue;
            }
            let x1 = BigInt(num1), x2 = BigInt(num2);
            let k = j;
            while (k < n) {
                let x3 = x1 + x2;
                let x3Str = x3.toString();
                if (num.slice(k, k + x3Str.length) !== x3Str) break;
                k += x3Str.length;
                x1 = x2;
                x2 = x3;
            }
            if (k === n) return true;
        }
    }
    return false;
};