• 27.3%

Additive number is a string whose digits can form 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 ‘0’-‘9’, write a function to determine if it’s an additive number.

How would you handle overflow for very large input integers?

0ms concise C++ solution (perfectly handles the follow-up and leading 0s)

use a helper function to add two strings.

Choose first two number then recursively check.

Note that the length of first two numbers can’t be longer than half of the initial string, so the two loops in the first function will end when i>num.size()/2 and j>(num.size()-i)/2, this will actually save a lot of time.

Update the case of heading 0s

e.g. “100010” should return false

https://discuss.leetcode.com/topic/29871/my-simple-c-non-recursion-solution

My Simple C++ Non-recursion Solution

https://discuss.leetcode.com/topic/29856/java-recursive-and-iterative-solutions

Java Recursive and Iterative Solutions

The idea is quite straight forward. Generate the first and second of the sequence, check if the rest of the string match the sum recursively. i and j are length of the first and second number. i should in the range of [0, n/2]. The length of their sum should >= max(i,j)

Java Recursive

Since isValid is a tail recursion it is very easy to turn it into a loop.

Java Iterative

If no overflow, instead of BigInteger we can consider to use Long which is a lot faster.

Java Iterative Using Long

https://discuss.leetcode.com/topic/30453/java-very-straightforward-solution-with-detailed-explanation

Java very straightforward solution with detailed explanation

The idea is quite straightforward:

1. Choose the first number A, it can be the leftmost 1 up to i digits. i<=(L-1)/2 because the third number should be at least as long as the first number

2. Choose the second number B, it can be the leftmost 1 up to j digits excluding the first number. the limit for j is a little bit tricky, because we don’t know whether A or B is longer. The remaining string (with length L-j) after excluding A and B should have a length of at least max(length A, length B), where length A = i and length B = j-i, thus L-j >= max(j-i, i)

3. Calls the recursive checker function and returns true if passes the checker function, or continue to the next choice of B (A) until there is no more choice for B or A, in which case returns a false.

Here is the code in Java:

If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java

https://discuss.leetcode.com/topic/29868/backtracking-with-pruning-java-3-ms-solution-and-python-48-ms-solution

Backtracking with Pruning: Java 3 ms Solution and Python 48 ms Solution

Backtracking with Pruning.

Java (3 ms):

Python (48 ms):

python

72ms, 8.93%, October 18, 2016

https://discuss.leetcode.com/topic/29845/python-solution

Just trying all possibilities for the first two numbers and checking whether the rest fits.