Skip to main content
Talentd

Additive Number - Solution & Explanation

MediumStringBacktracking9 min readAsked at: Meta, Google, Epic Systems
Practice this problem

Problem Statement

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?

Approach Overview

Problem Overview: You are given a numeric string num. The task is to determine whether it can form an additive sequence. In an additive sequence, every number (starting from the third) equals the sum of the previous two. Numbers cannot have leading zeros unless the number itself is 0.

Approach 1: Recursive Backtracking with Early Termination (O(n^3) time, O(n) space)

This approach tries all possible ways to split the first two numbers in the string, then recursively verifies whether the remaining string follows the additive rule. Start by choosing indices i and j to define the first two numbers. Convert them to integers (or use string-based addition to avoid overflow), compute their sum, and check if the next part of the string begins with that value. If it matches, continue the process recursively with the new pair. Early termination happens when a generated sum does not match the next substring, which prunes large parts of the search tree. The method naturally fits a backtracking pattern because you explore candidate splits and abandon invalid sequences quickly. Parsing and substring comparisons lead to O(n^3) time in the worst case, while recursion depth and substring storage require O(n) space.

Approach 2: Iterative Approach with Two Pointers (O(n^3) time, O(1) space)

This approach removes recursion and checks sequences iteratively. First, iterate over all possible splits for the first and second numbers using two pointers. After fixing these two values, simulate the additive sequence by repeatedly computing their sum and checking if the next substring matches it. If it matches, move the pointers forward and continue with the new pair. If any mismatch occurs, break early and try another split. Since you only track a few indices and temporary values, the extra space stays at O(1). However, generating candidate pairs and validating the remaining substring still leads to O(n^3) time complexity in the worst case. The approach mainly relies on careful string manipulation and controlled pointer movement similar to patterns used in two pointers problems.

Recommended for interviews: The recursive backtracking solution is usually preferred in interviews because it clearly expresses the search space and shows that you can prune invalid paths early. Interviewers expect you to handle leading zeros, large number addition, and substring validation carefully. The iterative version demonstrates strong control over pointer logic and space optimization. Showing the brute-force split idea first, then refining it with early termination, signals strong problem-solving skills.

Approach 1: Recursive Backtracking with Early Termination

This approach involves splitting the string into two initial numbers and trying to build valid subsequent numbers recursively. We backtrack if at any point the sequence condition is not met.

The solution defines a helper function is_valid that attempts to recursively verify the additive condition. We iterate over possible first and second numbers, ensuring no number has a leading zero unless it's single-digit. Backtracking is used when conditions fail at any step.

Code

PythonC

Python

C

Complexity

Time Complexity: O(2^(N/2)), where N is the length of the string.
Space Complexity: O(N) due to recursion stack.

Try this approach in the editor →

Approach 2: Iterative Approach with Two Pointers

This method uses two pointers to check possible partitions iteratively rather than recursively, aiming for reduced overhead and complexity by avoiding recursion.

This Java solution leverages an iterative strategy with two pointers to avoid recursion. The method isValid checks the subsequent numbers by adjusting the indices accurately given two beginning numbers. Iteration continues only when the string matches the summation condition.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(2^(N/2)) due to nested loops.
Space Complexity: O(1) since recursion is avoided.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Backtracking with Early Termination

Time Complexity: O(2^(N/2)), where N is the length of the string.
Space Complexity: O(N) due to recursion stack.

Iterative Approach with Two Pointers

Time Complexity: O(2^(N/2)) due to nested loops.
Space Complexity: O(1) since recursion is avoided.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Backtracking with Early TerminationO(n^3)O(n)Best for interviews when demonstrating recursive exploration and pruning invalid sequences
Iterative Two-Pointer ValidationO(n^3)O(1)Useful when avoiding recursion or when memory usage must stay minimal

Video Solution

Additive Number | LeetCode 306 | C++, Python • Knowledge Center • 13,370 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Additive Number easy or hard?
Additive Number is considered a medium difficulty problem. The main challenge is correctly generating candidate splits, preventing numbers with leading zeros, and validating the sequence without overflow issues when numbers become large.
Additive Number Python/Java solution
Python solutions typically use recursion with substring slicing and integer or string-based addition. Java implementations often simulate the sequence iteratively using indices and string comparisons. Both follow the same idea: choose two starting numbers and verify whether the remaining digits match their additive sums.
How to solve Additive Number in O(n)?
An O(n) solution is not feasible because you must try multiple splits for the first two numbers before validating the rest of the sequence. The fastest practical approaches run in O(n^3) time due to O(n^2) starting choices and substring checks. Optimization mainly comes from early termination when a sequence fails.
What is the best approach for Additive Number?
Recursive backtracking with early termination is the most common approach. It tries all valid splits for the first two numbers and recursively checks whether the rest of the string follows the additive rule. Pruning invalid branches early keeps the search manageable. The overall time complexity is O(n^3) with O(n) recursion space.
Is Additive Number asked at Google/Amazon/Meta?
Additive Number is a classic string and backtracking problem that appears in technical interview practice sets and has been reported in interviews at companies like Amazon and Google. It tests string parsing, recursion, and careful handling of edge cases such as leading zeros and large numbers.
What data structure is used in Additive Number?
The problem mainly relies on string manipulation and arithmetic operations rather than complex data structures. Backtracking solutions use recursion to explore candidate sequences, while iterative approaches rely on pointer indices and substring comparisons.
What is the time complexity of Additive Number?
The typical solution runs in O(n^3) time. You try O(n^2) combinations for the first two numbers, and for each pair you may scan the rest of the string to validate the additive sequence. Space complexity ranges from O(1) in iterative solutions to O(n) with recursion.

Ready to solve this problem?

Practice Additive Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Split Array into Fibonacci Sequence