306. Additive Number

[ Problem ]

An additive number is a string whose digits can form an additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits, return true if it is an additive number or false otherwise.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

 

Example 1:

Input: "112358"

Output: true

Explanation: 

The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"

Output: true

Explanation: 

The additive sequence is: 1, 99, 100, 199. 

1 + 99 = 100, 99 + 100 = 199

 

Constraints:

• 1 <= num.length <= 35
• num consists only of digits.

[ Solution ]

1. 

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        ret = False
        def solve(n1: int, n2: int, remain: str):
            if not (len(remain) > 1 and remain[0] == '0') and n1 + n2 == int(remain):
                nonlocal ret
                ret = True
                return
            if n1 == -1:
                for idx in range(1, len(remain)):
                    sub = remain[idx:]
                    n3 = remain[:idx]
                    if len(n3) > 1 and n3[0] == '0':
                        continue
                    if int(sub) >= int(n3):
                        solve(n2, int(n3), sub)
            else:
                sum = n1 + n2
                size = len(str(sum))
                sub = remain[size:]
                n3 = int(remain[:size])
                if sum == n3:
                    solve(n2, n3, sub)

        solve(-1, -1, num)
        return ret

 

2. 

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
      def dfs(s, seq):        
        if not s:  
            if len(seq) > 2: 
                  return True
            else: 
              return False
              
        for i in range(len(s)):
            if s[0] == '0' and i > 0: 
              break
            cur = int(s[:i+1]) 
            if len(seq) > 1 and cur != seq[-2] + seq[-1]: 
              continue
            if dfs(s[i+1:], seq+[cur]): return True                 
        return False
    
      return dfs(num, [])