# Question

Formatted question description: https://leetcode.ca/all/306.html

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.

Follow up: How would you handle overflow for very large input integers?

# Algorithm

Let the first digit start with one digit, and the second digit will be searched for higher digits. The first two digits are confirmed, and the third digit is obtained by adding them.

The three arrays are arranged to form a string, which is the same length as the original string if it is less than the original length, then take out the second and third numbers from the previous calculation, and use the same method to get the third number, then add the current string, and then sum Compared to the original string length.

# Code

• import java.util.ArrayList;

public static void main(String[] args) {
Solution s = out.new Solution();

}

// very good follow up analysis
class Solution {

boolean isFound = false;

if (num == null || num.length() == 0) {
return false;
}

dfs(num, 0, new ArrayList<Long>());

return isFound;
}

private void dfs(String num, int startIndex, ArrayList<Long> out) {

if (isFound) {
return;
}

if (startIndex == num.length()) {
// @note: input is [1,2], then should return false
// @note: not working if ==3, must be >=3
//          input: "112358", out will be "[1, 1, 2, 3, 5, 8]"
if (out.size() >= 3) {
isFound = true;
}
return;
}

for (int i = startIndex; i < num.length(); i++) {

String current = num.substring(startIndex, i + 1); // @note：+1

// skip invalid
// 检测str的长度大于19就break，因为long的十进制数长度是19位
if ((current.length() > 1 && current.charAt(0) == '0') || current.length() > 19) {
}

long curNum = Long.valueOf(current);
long n = (long) out.size();

if (out.size() >= 2 && curNum != out.get((int) (n - 1)) + out.get((int) (n - 2))) {
continue;
}

dfs(num, i + 1, out);
out.remove(out.size() - 1);
}
}
}
}

############

class Solution {
int n = num.length();
for (int i = 1; i < Math.min(n - 1, 19); ++i) {
for (int j = i + 1; j < Math.min(n, i + 19); ++j) {
if (i > 1 && num.charAt(0) == '0') {
break;
}
if (j - i > 1 && num.charAt(i) == '0') {
continue;
}
long a = Long.parseLong(num.substring(0, i));
long b = Long.parseLong(num.substring(i, j));
if (dfs(a, b, num.substring(j))) {
return true;
}
}
}
return false;
}

private boolean dfs(long a, long b, String num) {
if ("".equals(num)) {
return true;
}
if (a + b > 0 && num.charAt(0) == '0') {
return false;
}
for (int i = 1; i < Math.min(num.length() + 1, 19); ++i) {
if (a + b == Long.parseLong(num.substring(0, i))) {
if (dfs(b, a + b, num.substring(i))) {
return true;
}
}
}
return false;
}
}

• class Solution:
def isAdditiveNumber(self, num: str) -> bool:

def dfs(startIndex: int, out: List[int]) -> bool:
# equal check is here
if len(out) >= 3 and out[-1] != out[-2] + out[-3]:
return False
if startIndex == len(num):
return len(out) >= 3

for i in range(startIndex, len(num)):
current = num[startIndex: i + 1]
if (len(current) > 1 and current[0] == '0'):
break

out.append(int(current))
if dfs(i + 1, out):
return True
out.pop()

return False

if not num:
return False
return dfs(0, [])

class Solution:
def isAdditiveNumber(self, num: str) -> bool:
def dfs(a, b, num):
if not num:
return True
if a + b > 0 and num[0] == '0':
return False
for i in range(1, len(num) + 1):
if a + b == int(num[:i]):
if dfs(b, a + b, num[i:]):
return True
return False

n = len(num)
for i in range(1, n - 1): # 1st cut
if i > 1 and num[0] == '0': # 0 + 1 = 1 is fine, but 00 + 1 is wrong
break
for j in range(i + 1, n): # 2nd cut, so making it a 3-segments
if j - i > 1 and num[i] == '0':
break
if dfs(int(num[:i]), int(num[i:j]), num[j:]): # better than below, early stop
return True
return False

########

class Solution(object):
"""
:type num: str
:rtype: bool
"""
n = len(num)
for x in range(0, n / 2):
if x > 0 and num[0] == "0":
break
for y in range(x + 1, n):
if y - x > 1 and num[x + 1] == "0":
break
i, j, k = 0, x, y
while k < n:
a = int(num[i:j + 1])
b = int(num[j + 1:k + 1])
if not num.startswith(add, k + 1):
break
if len(add) + 1 + k == len(num):
return True
i = j + 1
j = k
return False


• class Solution {
public:
int n = num.size();
for (int i = 1; i < min(n - 1, 19); ++i) {
for (int j = i + 1; j < min(n, i + 19); ++j) {
if (i > 1 && num[0] == '0') break;
if (j - i > 1 && num[i] == '0') continue;
auto a = stoll(num.substr(0, i));
auto b = stoll(num.substr(i, j - i));
if (dfs(a, b, num.substr(j, n - j))) return true;
}
}
return false;
}

bool dfs(long long a, long long b, string num) {
if (num == "") return true;
if (a + b > 0 && num[0] == '0') return false;
for (int i = 1; i < min((int) num.size() + 1, 19); ++i)
if (a + b == stoll(num.substr(0, i)))
if (dfs(b, a + b, num.substr(i, num.size() - i)))
return true;
return false;
}
};

• func isAdditiveNumber(num string) bool {
n := len(num)
var dfs func(a, b int64, num string) bool
dfs = func(a, b int64, num string) bool {
if num == "" {
return true
}
if a+b > 0 && num[0] == '0' {
return false
}
for i := 1; i < min(len(num)+1, 19); i++ {
c, _ := strconv.ParseInt(num[:i], 10, 64)
if a+b == c {
if dfs(b, c, num[i:]) {
return true
}
}
}
return false
}
for i := 1; i < min(n-1, 19); i++ {
for j := i + 1; j < min(n, i+19); j++ {
if i > 1 && num[0] == '0' {
break
}
if j-i > 1 && num[i] == '0' {
continue
}
a, _ := strconv.ParseInt(num[:i], 10, 64)
b, _ := strconv.ParseInt(num[i:j], 10, 64)
if dfs(a, b, num[j:]) {
return true
}
}
}
return false
}

func min(a, b int) int {
if a < b {
return a
}
return b
}