https://leetcode.com/problems/additive-number/
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.
For example:
"112358" is an additive number because 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
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.
Solution
This is a permutation a like problem. The key to solve it is to build the first number and second number. Then we check if string is an additive number started by the 2 number. Let len1 is the length of number1, len2 for number2, n for length of string. So, the length of the next number should be greater than or equal to max(len1, len2). So we have condition that n – len1 + len2 >= max(len1, len2)
Then we should write isValid(String str, int i, int j) function to check if str is a additive number with first number [0,…,i], second number is [i+1,…,j]. When writing this function, we should eliminate exception number like ‘012’, ’01’. On the other hand, we should pay attention that ‘0’ is a valid number.
check my code on github: link