LeetCode Solutions Blog

Additive Number

Number: 306

Difficulty: Medium

Paid? No

Problem Description

Given a string containing only digits, determine if it can form an additive sequence. An additive sequence is a sequence of at least three numbers where, except for the first two numbers, each number is the sum of the two preceding ones. Numbers in the sequence must not have leading zeros unless the number itself is 0.

Key Insights

The problem requires checking all possible splits for the first two numbers.
Use backtracking (recursion) to simulate the additive sequence formation.
Handle cases where a number might have a leading zero.
Big integers can be managed using the language’s built-in capabilities (Python, Java’s BigInteger, etc.) or by treating numbers as strings in languages that do not support arbitrary precision.

Space and Time Complexity

Time Complexity: O(n^3) in the worst-case scenario due to the nested loops for splitting the string and recursive validation of sequences. Space Complexity: O(n) due to recursion call stack and substring operations.

Solution

The solution uses a backtracking approach to generate potential first and second numbers. For each candidate pair, it recursively checks if the remaining substring conforms to the additive sequence property. The algorithm carefully avoids numbers with leading zeros except for the digit '0'. The recursion tries to match the sum of the previous two numbers with the next portion of the string and continues until either the string is consumed or a mismatch occurs.

Code Solutions

def isAdditiveNumber(num):
    # Helper function to perform backtracking.
    # index: current index in num string,
    # num1 and num2: the last two numbers of the current sequence,
    # count: number of numbers in the current sequence.
    def backtrack(index, num1, num2, count):
        # If we have consumed the entire string and found at least 3 numbers, return True.
        if index == len(num):
            return count >= 3
        
        # Calculate the expected sum of the latest two numbers.
        expected_sum = num1 + num2
        expected_str = str(expected_sum)
        # Check if the next part of the string starts with this sum.
        if not num.startswith(expected_str, index):
            return False
        
        # If it matches, continue backtracking.
        return backtrack(index + len(expected_str), num2, expected_sum, count + 1)
    
    n = len(num)
    # Try every possible split for the first number and second number.
    for i in range(1, n):
        # Avoid numbers with leading zeros.
        if num[0] == '0' and i > 1:
            break
        num1 = int(num[:i])
        for j in range(i + 1, n):
            # Avoid numbers with leading zeros.
            if num[i] == '0' and j - i > 1:
                break
            num2 = int(num[i:j])
            # If the remaining string can form a valid sequence starting with num1 and num2, return True.
            if backtrack(j, num1, num2, 2):
                return True
    return False

# Example usage:
print(isAdditiveNumber("112358"))    # Output: True
print(isAdditiveNumber("199100199")) # Output: True