Solution: Additive Number
Explore the backtracking technique to determine if a given string represents an additive number sequence. Learn how to recursively partition the string, enforce no leading zeros, and verify the sum condition for all subsequent numbers. This lesson helps you implement an O(n³) time solution that systematically tests possible sequences until it finds a valid additive series or concludes none exists.
We'll cover the following...
Statement
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...