• Time:O(n^2)
• Space:O(n)

## C++

class Solution {
public:
const int n = num.length();

// num[0..i] = firstNum
for (int i = 0; i < n / 2; ++i) {
if (i > 0 && num[0] == '0')
return false;
const long firstNum = stol(num.substr(0, i + 1));
// num[i + 1..j] = secondNum
// len(thirdNum) >= max(len(firstNum), len(secondNum))
for (int j = i + 1; max(i, j - i) < n - j; ++j) {
if (j > i + 1 && num[i + 1] == '0')
break;
const long secondNum = stol(num.substr(i + 1, j - i));
if (dfs(num, firstNum, secondNum, j + 1))
return true;
}
}

return false;
}

private:
bool dfs(const string& num, long firstNum, long secondNum, long s) {
if (s == num.length())
return true;

const long thirdNum = firstNum + secondNum;
const string& thirdNumStr = to_string(thirdNum);
return num.find(thirdNumStr, s) == s &&
dfs(num, secondNum, thirdNum, s + thirdNumStr.length());
}
};

## JAVA

class Solution {
final int n = num.length();

// num[0..i] = firstNum
for (int i = 0; i < n / 2; ++i) {
if (i > 0 && num.charAt(0) == '0')
return false;
final long firstNum = Long.parseLong(num.substring(0, i + 1));
// num[i + 1..j] = secondNum
// len(thirdNum) >= max(len(firstNum), len(secondNum))
for (int j = i + 1; Math.max(i, j - i) < n - j; ++j) {
if (j > i + 1 && num.charAt(i + 1) == '0')
break;
final long secondNum = Long.parseLong(num.substring(i + 1, j + 1));
if (dfs(num, firstNum, secondNum, j + 1))
return true;
}
}

return false;
}

private boolean dfs(final String num, long firstNum, long secondNum, long s) {
if (s == num.length())
return true;

final long thirdNum = firstNum + secondNum;
final String thirdNumStr = String.valueOf(thirdNum);
return num.indexOf(thirdNumStr, (int) s) == s &&
dfs(num, secondNum, thirdNum, s + thirdNumStr.length());
}
}

## Python

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

def dfs(firstNum: int, secondNum: int, s: int) -> bool:
if s == len(num):
return True

thirdNum = firstNum + secondNum
thirdNumStr = str(thirdNum)

return num.find(thirdNumStr, s) == s and dfs(secondNum, thirdNum, s + len(thirdNumStr))

# num[0..i] = firstNum
for i in range(n // 2):
if i > 0 and num[0] == '0':
return False
firstNum = int(num[:i + 1])
# num[i + 1..j] = secondNum
# len(thirdNum) >= max(len(firstNum), len(secondNum))
j = i + 1
while max(i, j - i) < n - j:
if j > i + 1 and num[i + 1] == '0':
break
secondNum = int(num[i + 1:j + 1])
if dfs(firstNum, secondNum, j + 1):
return True
j += 1

return False