LeetCode 306 - Additive Number

The problem asks us to determine whether a given string of digits can be partitioned into a valid additive sequence. An additive sequence is a sequence of numbers where: - There are at least three numbers.

leetcodemediumstringbacktracking

LeetCode Problem 306

Difficulty: 🟡 Medium
Topics: String, Backtracking

Solution

Problem Understanding

The problem asks us to determine whether a given string of digits can be partitioned into a valid additive sequence.

An additive sequence is a sequence of numbers where:

  • There are at least three numbers.
  • Every number after the first two is equal to the sum of the previous two numbers.
  • No number is allowed to contain leading zeros unless the number itself is exactly "0".

The input is a single string num containing only numeric characters. We are not given separators between numbers, so our task is to determine whether there exists some way to split the string into valid numbers that satisfy the additive property.

For example, the string "112358" can be split as:

  • 1
  • 1
  • 2
  • 3
  • 5
  • 8

Each number is the sum of the previous two:

  • 1 + 1 = 2
  • 1 + 2 = 3
  • 2 + 3 = 5
  • 3 + 5 = 8

Therefore the result is true.

The constraints are relatively small:

  • 1 <= num.length <= 35

This is important because it suggests we can afford to try many possible splits of the first two numbers. However, the values themselves may become very large, potentially exceeding normal integer ranges in some languages. This is why the follow-up asks about overflow handling.

Several edge cases are especially important:

  • Numbers with leading zeros are invalid unless the number is exactly "0".
  • Very short strings cannot form an additive sequence because at least three numbers are required.
  • Multiple possible splits may exist, so we cannot greedily choose only one partition.
  • Large numeric values may overflow fixed-width integer types in languages like Go or Java.

The key challenge is correctly trying all valid starting pairs while efficiently verifying the rest of the sequence.

Approaches

Brute Force Approach

The brute-force idea is to try every possible partitioning of the string into multiple numbers and check whether the resulting sequence satisfies the additive condition.

For a string of length n, every position between digits can either contain a split or not contain a split. That creates approximately 2^(n-1) possible partitions. For each partition, we would parse the numbers and verify whether each number equals the sum of the previous two.

This approach is correct because it exhaustively checks every possible sequence. If a valid additive sequence exists, brute force will eventually find it.

However, it is far too slow. The number of possible partitions grows exponentially with the string length, making it impractical even for moderate input sizes.

Optimal Backtracking / Simulation Approach

The key observation is that once the first two numbers are chosen, the entire sequence is completely determined.

Suppose we pick:

  • first number = a
  • second number = b

Then:

  • third number must be a + b
  • fourth number must be b + (a + b)
  • and so on

This means we only need to enumerate all possible choices for the first two numbers. After that, we can deterministically verify whether the remaining string matches the expected sums.

Since the first two numbers uniquely define the sequence, we reduce the search space dramatically.

We also carefully handle leading zeros:

  • "0" is valid
  • "01" is invalid

This approach uses controlled backtracking and string matching, which is efficient enough for the problem constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries every possible partition of the string
Optimal O(n^3) O(n) Tries all first and second numbers, then validates deterministically

Algorithm Walkthrough

Optimal Algorithm

  1. Iterate over all possible endings of the first number.

The first number starts at index 0. We try every possible length for it. If the number starts with '0' and has more than one digit, we stop immediately because leading zeros are invalid. 2. For each first number, iterate over all possible endings of the second number.

The second number begins immediately after the first number. Again, if it starts with '0' and has multiple digits, we skip it. 3. Convert the first and second substrings into integers.

These become the starting pair of the additive sequence. 4. Start validating the remainder of the string.

Compute:

next_number = first + second

Convert this sum into a string because we need to compare it directly against the corresponding substring in num. 5. Check whether the remaining string starts with the expected sum.

If it does not match exactly, this starting pair is invalid. 6. If the expected sum matches, advance forward in the string.

Update:

first = second
second = next_number

Continue checking the next expected value. 7. If we consume the entire string successfully, return true.

This means every segment matched the additive property. 8. If all starting pairs fail, return false.

Why it works

The correctness comes from the fact that an additive sequence is completely determined by its first two numbers. Once those are fixed, every later number has exactly one valid value. Therefore, trying all possible first and second numbers guarantees that we will find a valid sequence if one exists.

The algorithm also correctly rejects invalid leading zeros and ensures the entire string is consumed without leftover digits.

Python Solution

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)

        def is_valid(first: int, second: int, start: int) -> bool:
            while start < n:
                next_num = first + second
                next_str = str(next_num)

                if not num.startswith(next_str, start):
                    return False

                start += len(next_str)
                first, second = second, next_num

            return True

        for i in range(1, n):
            if num[0] == '0' and i > 1:
                break

            first = int(num[:i])

            for j in range(i + 1, n):
                if num[i] == '0' and j - i > 1:
                    break

                second = int(num[i:j])

                if is_valid(first, second, j):
                    return True

        return False

The implementation begins by storing the length of the string so it can be reused efficiently.

The helper function is_valid performs the deterministic validation phase. It receives the first two numbers and the current index in the string. Inside the loop, it repeatedly computes the next expected value, converts it into a string, and checks whether the remaining substring begins with that value.

The expression:

num.startswith(next_str, start)

is particularly useful because it avoids manual substring slicing logic and directly checks whether the expected sum appears at the current position.

The outer loops enumerate every valid choice for the first and second numbers. The leading zero checks are critical:

if num[0] == '0' and i > 1:

prevents invalid first numbers like "01".

Similarly:

if num[i] == '0' and j - i > 1:

prevents invalid second numbers like "02".

As soon as a valid sequence consumes the entire string, the function returns True. If no starting pair works, the answer is False.

Go Solution

package main

import "strconv"

func isAdditiveNumber(num string) bool {
	n := len(num)

	isValid := func(first, second int64, start int) bool {
		for start < n {
			nextNum := first + second
			nextStr := strconv.FormatInt(nextNum, 10)

			if start+len(nextStr) > n {
				return false
			}

			if num[start:start+len(nextStr)] != nextStr {
				return false
			}

			start += len(nextStr)
			first, second = second, nextNum
		}

		return true
	}

	for i := 1; i < n; i++ {
		if num[0] == '0' && i > 1 {
			break
		}

		first, _ := strconv.ParseInt(num[:i], 10, 64)

		for j := i + 1; j < n; j++ {
			if num[i] == '0' && j-i > 1 {
				break
			}

			second, _ := strconv.ParseInt(num[i:j], 10, 64)

			if isValid(first, second, j) {
				return true
			}
		}
	}

	return false
}

The Go implementation follows the same logic as the Python version but uses int64 and the strconv package for integer conversion.

One important difference is overflow handling. Python integers automatically expand to arbitrary precision, but Go's int64 has a fixed limit. For extremely large inputs, overflow could occur. A production-grade solution could avoid integer parsing entirely and instead perform string-based addition.

The substring checks are implemented manually using slicing:

num[start:start+len(nextStr)]

because Go does not have Python's startswith helper.

Worked Examples

Example 1

Input:

"112358"

We try possible splits.

Attempt 1

First Second Remaining Expected Next Match
1 1 2358 2 Yes
1 2 358 3 Yes
2 3 58 5 Yes
3 5 8 8 Yes

The string is fully consumed, so the result is true.

Example 2

Input:

"199100199"

Attempt 1

First Second Remaining Expected Next Match
1 99 100199 100 Yes
99 100 199 199 Yes

The entire string is consumed successfully.

Result:

true

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) Two nested loops choose first and second numbers, validation may scan the remaining string
Space O(n) Temporary strings created during sum conversion

The outer two loops generate all possible pairs of starting numbers. There are approximately O(n^2) such pairs. For each pair, validation may scan up to the entire remaining string, which costs O(n) time.

The algorithm therefore runs in O(n^3) time overall.

The auxiliary space is primarily due to string conversions when computing expected sums.

Test Cases

solution = Solution()

assert solution.isAdditiveNumber("112358") == True      # classic Fibonacci-style sequence
assert solution.isAdditiveNumber("199100199") == True  # varying digit lengths
assert solution.isAdditiveNumber("123") == True        # minimal valid sequence
assert solution.isAdditiveNumber("1023") == False      # invalid leading zero
assert solution.isAdditiveNumber("000") == True        # all zeros is valid
assert solution.isAdditiveNumber("011235") == True     # leading zero allowed only for single digit zero
assert solution.isAdditiveNumber("101") == True        # 1,0,1
assert solution.isAdditiveNumber("1203") == False      # invalid partitioning
assert solution.isAdditiveNumber("111") == False       # cannot satisfy additive property
assert solution.isAdditiveNumber("12122436") == True   # 12,12,24,36
assert solution.isAdditiveNumber("1") == False         # too short
assert solution.isAdditiveNumber("12") == False        # fewer than 3 numbers
assert solution.isAdditiveNumber("198019823962") == True  # larger values
Test Why
"112358" Standard additive sequence
"199100199" Handles changing digit lengths
"123" Smallest typical valid example
"1023" Rejects leading zero in middle number
"000" Valid sequence consisting entirely of zeros
"011235" Allows single zero correctly
"101" Tests zero handling inside sequence
"1203" Detects invalid continuation
"111" Fails additive property
"12122436" Multi-digit additive numbers
"1" Input too short
"12" Cannot form three numbers
"198019823962" Larger numeric values

Edge Cases

Leading Zeros

Leading zeros are the most common source of bugs in this problem. For example:

"1023"

A naive implementation might incorrectly accept:

1, 02, 3

However, "02" is invalid because numbers cannot contain leading zeros unless the number itself is exactly "0".

The implementation handles this by immediately stopping exploration whenever a multi-digit number starts with '0'.

All Zeros

The input:

"000"

is actually valid because it can be interpreted as:

0, 0, 0

and:

0 + 0 = 0

Some implementations mistakenly reject all numbers beginning with zero. The correct rule is that single-digit zero is allowed.

Large Integer Values

The string length can reach 35 digits, which may exceed 64-bit integer ranges.

Python handles this naturally because integers have arbitrary precision. In Go or Java, using fixed-width integers can overflow.

A more robust approach for production systems would implement string-based addition rather than integer conversion. That avoids overflow entirely and correctly supports arbitrarily large values.