# Additive Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/additive-number)
Canonical: https://scaleengineer.com/dsa/problems/additive-number
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String
**Companies:** [Epic Systems](https://scaleengineer.com/companies/epic-systems)
---
## Problem
An **additive number** is a string whose digits can form an **additive sequence**.

A valid **additive sequence** should contain **at least** three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits, return `true` if it is an **additive number** or `false` otherwise.

**Note:** Numbers in the additive sequence **cannot** have leading zeros, so sequence `1, 2, 03` or `1, 02, 3` is invalid.

**Example 1:**

**Input:** "112358"
**Output:** true
**Explanation:** 
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

**Example 2:**

**Input:** "199100199"
**Output:** true
**Explanation:** 
The additive sequence is: 1, 99, 100, 199. 
1 + 99 = 100, 99 + 100 = 199

**Constraints:**

* `1 <= num.length <= 35`
* `num` consists only of digits.

**Follow up:** How would you handle overflow for very large input integers?

# Approaches
## Brute-Force All Partitions
This is a highly inefficient approach that explores every possible way to partition the input string into a sequence of numbers. For each partition, it checks if the sequence is additive. This method is primarily for demonstrating a naive solution and understanding the problem space.
**Time:** O(2^n * n). The number of ways to partition a string of length `n` is `2^(n-1)`. Validating each partition takes `O(n)` time, as it involves string additions and comparisons over the length of the string. · **Space:** O(n). The recursion depth can go up to `n`, and the list storing the current partition can also take `O(n)` space.
**Pros:** Conceptually simple to understand as it directly models the problem of finding a valid partition.
**Cons:** Extremely slow due to its exponential time complexity.; Impractical for the given constraints (n <= 35) and will time out.
### Explanation
The core idea is to use recursion or backtracking to generate all `2^(n-1)` possible partitions of the string. A function `generate(index, current_partition)` would try to form a number starting at `index` and ending at `k` (where `k` goes from `index` to `n-1`). For each number formed, it's added to `current_partition`, and the function recurses from `k+1`. When a full partition is formed (i.e., `index == n`), it's validated. The validation step checks if it's an additive sequence with at least three numbers, where each number after the second is the sum of the two preceding ones. Due to the large number of possible partitions, this approach is not feasible for the given constraints.
### Algorithm
- 1. Define a recursive function `find(index, partition)` to generate all possible partitions of the input string `num`.
- 2. The base case for the recursion is when `index` reaches the end of the string. At this point, a complete partition has been formed.
- 3. Once a partition is formed, check if it represents a valid additive sequence. A sequence is additive if it has at least three numbers and each number after the second is the sum of the two preceding ones.
- 4. In the recursive step, loop from `k = index` to `n-1` to form the next number in the partition, `s = num.substring(index, k+1)`.
- 5. Handle leading zeros: if `s` has more than one digit and starts with '0', it's an invalid number, so this path is pruned.
- 6. Add the valid number `s` to the current `partition` and make a recursive call: `find(k+1, partition)`. After the call returns, backtrack by removing `s` to explore other possibilities.
- 7. The validation function, say `isAdditive(partition)`, will use a string addition helper to verify the sum property.
- 8. If any partition is found to be a valid additive sequence, the main function returns `true` immediately. If all partitions are explored without success, it returns `false`.

## Backtracking Search for First Two Numbers
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.
**Time:** O(n^3). The nested loops to pick the first two numbers have a complexity of `O(n^2)`. For each pair, the `checkSequence` function is called. The work done in one full path of `checkSequence` involves a series of string additions and comparisons. The total work is proportional to the sum of lengths of all numbers, which is `O(n)`. Thus, the validation for one pair is `O(n)`. Total complexity is `O(n^2) * O(n) = O(n^3)`. · **Space:** O(n). The space is dominated by the recursion stack depth of `checkSequence`, which can be at most `O(n)` (in the case of a sequence like "101123..."). The strings created during the process also contribute `O(n)` space.
**Pros:** Significantly more efficient than brute-forcing all partitions.; Passes within the time limits for the given constraints.; The logic is a direct and structured way to search for the solution.
**Cons:** The complexity is polynomial, which might be slow for very large `n` (though `n=35` is fine).; Requires careful implementation of string addition and handling of edge cases like leading zeros.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

```java
class Solution { public boolean isAdditiveNumber ( String num ) { int n = num . length (); for ( int i = 1 ; i < Math . min ( n - 1 , 19 ); ++ i ) { for ( int j = i + 1 ; j < Math . min ( n , i + 19 ); ++ j ) { if ( i > 1 && num . charAt ( 0 ) == '0' ) { break ; } if ( j - i > 1 && num . charAt ( i ) == '0' ) { continue ; } long a = Long . parseLong ( num . substring ( 0 , i )); long b = Long . parseLong ( num . substring ( i , j )); if ( dfs ( a , b , num . substring ( j ))) { return true ; } } } return false ; } private boolean dfs ( long a , long b , String num ) { if ( "" . equals ( num )) { return true ; } if ( a + b > 0 && num . charAt ( 0 ) == '0' ) { return false ; } for ( int i = 1 ; i < Math . min ( num . length () + 1 , 19 ); ++ i ) { if ( a + b == Long . parseLong ( num . substring ( 0 , i ))) { if ( dfs ( b , a + b , num . substring ( i ))) { return true ; } } } return false ; } }
```

### CPP

```cpp
class Solution { public: bool isAdditiveNumber ( string num ) { int n = num . size (); for ( int i = 1 ; i < min ( n - 1 , 19 ); ++ i ) { for ( int j = i + 1 ; j < min ( n , i + 19 ); ++ j ) { if ( i > 1 && num [ 0 ] == '0' ) break ; if ( j - i > 1 && num [ i ] == '0' ) continue ; auto a = stoll ( num . substr ( 0 , i )); auto b = stoll ( num . substr ( i , j - i )); if ( dfs ( a , b , num . substr ( j , n - j ))) return true ; } } return false ; } bool dfs ( long long a , long long b , string num ) { if ( num == "" ) return true ; if ( a + b > 0 && num [ 0 ] == '0' ) return false ; for ( int i = 1 ; i < min (( int ) num . size () + 1 , 19 ); ++ i ) if ( a + b == stoll ( num . substr ( 0 , i ))) if ( dfs ( b , a + b , num . substr ( i , num . size () - i ))) return true ; return false ; } };
```

### Python

```python
class Solution : def isAdditiveNumber ( self , num : str ) -> bool : def dfs ( startIndex : int , out : List [ int ]) -> bool : # equal check is here if len ( out ) >= 3 and out [ - 1 ] != out [ - 2 ] + out [ - 3 ]: return False if startIndex == len ( num ): return len ( out ) >= 3 for i in range ( startIndex , len ( num )): current = num [ startIndex : i + 1 ] if ( len ( current ) > 1 and current [ 0 ] == '0' ): break out . append ( int ( current )) if dfs ( i + 1 , out ): return True out . pop () return False if not num : return False return dfs ( 0 , []) ############# # follow up: super large number, solve overflow issue class Solution : def addStrings ( num1 : str , num2 : str ) -> str : carry = 0 result = [] i , j = len ( num1 ) - 1 , len ( num2 ) - 1 while i >= 0 or j >= 0 or carry : x = int ( num1 [ i ]) if i >= 0 else 0 y = int ( num2 [ j ]) if j >= 0 else 0 sum = x + y + carry result . append ( str ( sum % 10 )) carry = sum // 10 i , j = i - 1 , j - 1 return '' . join ( reversed ( result )) def isAdditiveNumber ( 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 ] if ( len ( num1 ) > 1 and num1 [ 0 ] == '0' ) or ( len ( num2 ) > 1 and num2 [ 0 ] == '0' ): continue while j < n : sum = addStrings ( num1 , num2 ) if not num . startswith ( sum , j ): break j += len ( sum ) num1 , num2 = num2 , sum if j == n : return True return False ############# class Solution : def isAdditiveNumber ( self , num : str ) -> bool : def dfs ( a , b , num ): if not num : return True if a + b > 0 and num [ 0 ] == '0' : return False for i in range ( 1 , len ( num ) + 1 ): if a + b == int ( num [: i ]): if dfs ( b , a + b , num [ i :]): return True return False n = len ( num ) for i in range ( 1 , n - 1 ): # 1st cut if i > 1 and num [ 0 ] == '0' : # 0 + 1 = 1 is fine, but 00 + 1 is wrong break for j in range ( i + 1 , n ): # 2nd cut, so making it a 3-segments if j - i > 1 and num [ i ] == '0' : break if dfs ( int ( num [: i ]), int ( num [ i : j ]), num [ j :]): # better than below, early stop return True return False
```