## Approach

The trick here is to choose only the first two numbers.

*What two numbers?*

Let’s understand this better by an example. Let’s say the given number, ‘N’ is 12315. In order to check ‘N’ is an additive number we choose the first number, let’s say ‘A’ as 12, and the second number, let’s say ‘B’ as 3. Now we can see that ‘A’ + ‘B’ = 12 + 3 = 15.

Once we choose these two numbers, later can be handled by recursion. But how are we going to choose the first two numbers? We will try all possible combinations and will come to a conclusion.

Let the first number be ‘A’, the second number be ‘B’, and the length of the string be ‘L’ then:

- For the first number ‘A’, it can be a minimum of 1 digit and can go up to ‘i’ digits where
*i <= (L - 1) / 2* because the third digit of the number should be at least as long as the first number.
- For the second number, ‘B’, it can be a minimum of 1 digit and can go up to ‘j’ digits, excluding the first number. The limit for ‘j’ is a little bit tricky because we don't know whether A or B is longer. The remaining string (with length L - j) after excluding ‘A’ and ‘B’ should have a length of at least max(length A, length B), where the length of A = i and length of B = j - i, thus L - j >= max( j - i, i).

*This might be a little overwhelming for you but bear with me for a few more minutes and you will get the intuition perfectly.*

*But now, what’s next?*

We will create a helper function **isAdditive()** which will take one string and two integers as its parameters and will check if these three are additive or not. Thus after selecting ‘A’ and ‘B’, we will call this function with the remaining string, and if it returns true, we will return true else, we will continue to the next choice of ‘B’ and ‘A’ until there is no more choice for ‘B’ or ‘A’. if we are left with no more choice for ‘B’ and ‘A’, we will return false.

*But how is this ***isAdditive()** going to be implemented?

This function will take three parameters ‘STR’, ‘NUM1’, ‘NUM2’. Base case would be very simple if it’s an empty string, then we will return true as we have reached the end of the string.

Then we will find out the sum of ‘NUM1’ and ‘NUM2’ representing ‘A’ and ‘B’ numerical values, respectively. If the sum(string form) is not a prefix of ‘STR’, then return false as it has to be an additive number as mentioned in the question. Else we will call this recursive function for the remaining string(string left after ‘SUM’ has been removed as its prefix ), ‘NUM2’, and integer value of ‘SUM’.

Below is the code for the above explanation

### Java

```
import java.util.*;
import java.lang.*;
import java.io.*;
class AdditiveNumber
{
public boolean isAdditive(String str, long num1, long num2)
{
// If we reach the end of the string, return true.
if (str.equals(""))
return true;
long sum = num1 + num2;
String s = ((Long)sum).toString();
// If the string does not start with sum of num1 and num2,
returns false.
if (!str.startsWith(s))
return false;
// Recursively checks for the remaining string.
return isAdditive(str.substring(s.length()), num2, sum);
}
public boolean isAdditiveNumber(String num)
{
int L = num.length();
// Loop to choose the first number 'A'.
for (int i = 1; i <= (L - 1) / 2; i++)
{
// 'A' cannot start with a 0 if its length is more
Than 1.
if (num.charAt(0) == '0' && i >= 2)
break;
// Loop to choose the second number 'B'.
for (int j = i + 1; L - j >= j - i && L - j >= i; j++)
{
// 'B' cannot start with a 0 if its length is more than 1.
if (num.charAt(i) == '0' && j - i >= 2)
break;
long num1 = Long.parseLong(num.substring(0, i));
long num2 = Long.parseLong(num.substring(i, j));
// Remaining String.
String substr = num.substring(j);
// Return true if isAdditive returns true.
if (isAdditive(substr, num1, num2))
return true; }
}
// No more combination possible, return false.
return false;
}
public static void main(String[] args)
{
AdditiveNumber ad = new AdditiveNumber();
Scanner myObj = new Scanner(System.in);
// Taking input.
String s1 = myObj.nextLine();
System.out.println(ad.isAdditiveNumber(s1));
}
}
```

### C++

```
#include<bits/stdc++.h>
using namespace std;
string sum(string s1,string s2){
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
string res; int c=0; int i=0;
for(; i<min(s1.length(),s2.length()); i++)
{
int n=(s1[i]-'0'+s2[i]-'0')+c;
res+=to_string(n%10);
c=n/10;
}
for(; i<s1.length(); i++)
{
int n=(s1[i]-'0')+c;
res+=to_string(n%10);
c=n/10;
}
for(; i<s2.length(); i++)
{
int n=(s2[i]-'0')+c;
res+=to_string(n%10);
c=n/10;
}
while(c!=0){
res+=to_string(c%10);
c=c/10;
}
reverse(res.begin(),res.end());
return res;
}
//backtracking function
bool check(string s1,string s2,string s)
{
if(s=="") return true;
string n=sum(s1,s2);
if(n==s.substr(0,n.length()) && check(s2,n,s.substr(n.length()))){
return true;
}
else{
return false;
}
}
bool isAdditiveNumber(string num) {
string s1,s2;
for(int i=1; i<num.length(); i++){
for(int j=i+1; j<num.length(); j++){
//creating first two numbers
s1=num.substr(0,i);
s2=num.substr(i,j-i);
//checking that the number contains leading 0's or not
if(s2[0]=='0' && s2.length()>1) continue;
string s=num.substr(j);
if(check(s1,s2,s)) return true;
}
}
return false;
}
int main()
{
string num;
cin>>num;
bool ans=isAdditiveNumber(num);
ans=ans?true:false;
cout<< boolalpha <<ans;
}
```

### Python

```
def isAdditiveNumber(num):
def add(prev,curr,index):
if index==len(num):
return 1
total=str(int(prev)+int(curr))
if total==num[index:index+len(total)]:
return add(curr,total,index+len(total))
else:
return False
for i in range(len(num)):
if num[0]=='0' and i>0:
break
for j in range(i+1,len(num)):
prev=num[0:i+1]
curr=num[i+1:j+1]
if curr[0]=='0' and len(curr)>1:
break
total=str(int(prev)+int(curr))
if total==num[j+1:j+1+len(total)]:
if add(curr,total,j+1+len(total)):
return True
return False
num=input()
print(isAdditiveNumber(num))
```

Input

```
112358
1234
```

Output

```
true
false
```

### Complexity Analysis

**Time Complexity**

**O(N ^ 2)**, where ‘N’ is the length of the string.

As we are using two nested for loops and each loop costs us O(N) time thus the overall time complexity is O(N ^ 2).

**Space Complexity**

The Space Complexity is** O(N)**, where ‘N’ is the length of the string.

As we are creating a recursive function which in the worst case would be called ‘N’ times so the space used by the recursion stack would be O(N).

Also check out - __Substr C++__

Must Read __Recursion in Data Structure__

## Frequently Asked Questions

### What is FIFO in Programming?

FIFO stands for First in First Out. It means that the element first inserted into the data structure is the first one to be processed. Example Queue

### What type of Data Structure is a string?

A string is a Linear Data Structure.

## Conclusion

We saw how we solved the additive number problem using recursion. You must be thrilled about learning a new concept but the road to becoming a recursion champ is still very long. So head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more.

**Recommended Readings:**

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!