Solution: Additive Number
Explore how to apply backtracking to determine if a digit string can form an additive sequence where each number is the sum of the previous two. Understand the step-by-step recursive process, handling of leading zeros, and time-space complexity to solve this problem efficiently.
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...