# Python 35 ms DFS

• The idea is simple. We do a DFS to find our two initial values for our tentative answer. These values are in the form of num[0...i] + num[i+1...j] such that 0 < i < j < len(num). These numbers will be first and second, respectively. From here: let num_start = j+1. Recursively, check the validity of the next number, where f_validity(next_number = num[num_start:k+1]) = next_number == first + second where num_start <= k < len(num). If valid, update next_number to k+1 and update our initial values to reflect our most recent addition. Return true if num_start is len(num).

Runtime should be O(n^3).

There are a few short circuits in the code, but they aren't essential to the argument.

``````class Solution(object):
def isAdditiveNumber(self, num):
for i in range(len(num)-2):
if num[0] == "0" and i > 0 or i > len(num) // 2: return False
for j in range(i+1, len(num)-1):
if j-1 > len(num) // 2 or num[i+1] == "0" and j > i + 1: break
num_start = j+1
first, second = int(num[0:i+1]), int(num[i+1:j+1])
count = 2
for k in range(j+1, len(num)):
if num[num_start] == "0" or k - num_start > len(num) // 2 or first + second < int(num[num_start:k+1]): break
elif first + second == int(num[num_start:k+1]):
first = second
second = int(num[num_start:k+1])
diff = k+1 - num_start
num_start += diff
k = num_start - 1
count += 1
if num_start == len(num) and count >= 3:return True
return False
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.