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" 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