Additive Number - Leetcode Solution

Additive Number Problem on Leetcode:

The Additive Number problem on Leetcode requires us to determine whether a given string can be split into a sequence of numbers such that the sum of any two adjacent numbers is equal to the next number in the sequence.

For example, "112358" can be split into [1,1,2,3,5,8] because 1+1=2, 1+2=3, 2+3=5, and 3+5=8.

To solve this problem, we can use a recursive approach where we start with the first and second numbers in the string and check whether they add up to a valid number. Then, if the sum is valid, we move on to the rest of the string recursively until we reach the end.

Here's the algorithm:

1. Define a recursive helper function that takes in three parameters: the remaining string num, the current index idx being processed, and the two previous numbers prev1 and prev2 that were added together to get the current number.

2. Base Case:

   a. If the index idx reaches the end of the string and we have at least three numbers in the sequence, we return True.

   b. If the index idx reaches the end of the string but we have less than three numbers in the sequence, we return False.

3. For each possible length of the current number cur_len starting from index idx, we check whether the current number is equal to the sum of prev1 and prev2.

4. If the current number is equal to the sum of prev1 and prev2, we recursively call the helper function with the updated parameters: the remaining string from index idx+cur_len, idx+cur_len as the new starting index, and prev2 and cur as the new previous numbers.

5. If any of the recursive calls return True, we return True from the current call. If none of them return True, we try the next possible length of cur_len.

6. If all possible lengths of cur_len have been tried and none of them returned True, we return False.

Here's the code implementation:

def isAdditiveNumber(num):
    def helper(num, idx, prev1, prev2):
        if idx == len(num) and len(seq) >= 3:
            return True
        elif idx == len(num):
            return False
        else:
            cur_len = 1
            while idx + cur_len <= len(num):
                cur = int(num[idx:idx+cur_len])
                if len(str(cur)) != cur_len:
                    return False
                if len(seq) <= 1 or prev1 + prev2 == cur:
                    if helper(num, idx+cur_len, prev2, cur):
                        return True
                cur_len += 1
            return False
    
    for i in range(1, len(num)):
        for j in range(i+1, len(num)):
            seq = [int(num[:i]), int(num[i:j])]
            if helper(num, j, seq[-2], seq[-1]):
                return True
    return False

The outer loop starts at index 1 because the first number cannot be of size 0. The inner loop starts at index i+1 to ensure that the second number is longer than the first.

We initialize the sequence of numbers seq with the first two numbers and call the helper function starting at index j where j is the length of the second number. We pass in the previous two numbers as prev2 and prev1 so that they can be used to calculate the current number.

If the helper function returns True, we have found a valid Additive number sequence and return True. If none of the combinations of the first two numbers work, we return False.

The time complexity of this solution is O(n^3) because the outer loop and inner loop go up to n, and for each combination of the first two numbers, the recursive helper function checks all possible lengths of the current number.

1