Similar Problems
Similar Problems not available
Additive Number  Leetcode Solution
Companies:
LeetCode: Additive Number Leetcode Solution
Difficulty: Medium
Topics: string backtracking
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:

Define a recursive helper function that takes in three parameters: the remaining string
num
, the current indexidx
being processed, and the two previous numbersprev1
andprev2
that were added together to get the current number. 
Base Case:
a. If the index
idx
reaches the end of the string and we have at least three numbers in the sequence, we returnTrue
.b. If the index
idx
reaches the end of the string but we have less than three numbers in the sequence, we returnFalse
. 
For each possible length of the current number
cur_len
starting from indexidx
, we check whether the current number is equal to the sum ofprev1
andprev2
. 
If the current number is equal to the sum of
prev1
andprev2
, we recursively call the helper function with the updated parameters: the remaining string from indexidx+cur_len
,idx+cur_len
as the new starting index, andprev2
andcur
as the new previous numbers. 
If any of the recursive calls return
True
, we returnTrue
from the current call. If none of them returnTrue
, we try the next possible length ofcur_len
. 
If all possible lengths of
cur_len
have been tried and none of them returnedTrue
, we returnFalse
.
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.
Additive Number Solution Code
1