An additive number is a string whose digits can be partitioned into an additive sequence.
A valid additive sequence contains at least three numbers, where every number after the first two is equal to the sum of the two immediately preceding numbers.
Given a string, num, containing only digits, determine whether it represents an additive number. Return TRUE if a valid additive sequence can be formed from the digits of num, and FALSE otherwise.
Note: Numbers in the additive sequence cannot have leading zeros. For example, the sequences
1, 2, 03and1, 02, 3are both invalid.
Constraints:
num.length
num consists only of digits.
The key intuition behind this problem is that once we fix the first two numbers in the sequence, the entire rest of the sequence is completely determined, each subsequent number must equal the sum of the two preceding ones. Therefore, we use backtracking to try all possible ways to choose the first and second numbers by varying their lengths, and for each choice, we greedily verify whether the remaining digits of the string can be partitioned to satisfy the additive property. The backtrack function processes the string from left to right, extracting candidate numbers of increasing length. For the first two numbers (count
An additive number is a string whose digits can be partitioned into an additive sequence.
A valid additive sequence contains at least three numbers, where every number after the first two is equal to the sum of the two immediately preceding numbers.
Given a string, num, containing only digits, determine whether it represents an additive number. Return TRUE if a valid additive sequence can be formed from the digits of num, and FALSE otherwise.
Note: Numbers in the additive sequence cannot have leading zeros. For example, the sequences
1, 2, 03and1, 02, 3are both invalid.
Constraints:
num.length
num consists only of digits.
The key intuition behind this problem is that once we fix the first two numbers in the sequence, the entire rest of the sequence is completely determined, each subsequent number must equal the sum of the two preceding ones. Therefore, we use backtracking to try all possible ways to choose the first and second numbers by varying their lengths, and for each choice, we greedily verify whether the remaining digits of the string can be partitioned to satisfy the additive property. The backtrack function processes the string from left to right, extracting candidate numbers of increasing length. For the first two numbers (count