hardBacktrackingPure DSA~35 min
Split a Digit String into a Fibonacci Sequence
A serialized ID is suspected to encode a Fibonacci-like sequence with separators stripped. Recover any valid split where each number equals the sum of the two before it.
Problem
Given a string num of digits, split it into a sequence of at least three non-negative integers f[0], f[1], ..., f[k] such that f[i] = f[i-1] + f[i-2] for i >= 2, no number has a leading zero (except the number 0 itself), and each fits in a signed 32-bit integer. Return any valid sequence, or an empty list if none exists.
Input
A string num of digit characters.
Output
A list of integers forming a valid Fibonacci-like split, or an empty list.
Constraints
- 1 <= num.length <= 200
- num consists of digits only.
- Each value must be <= 2^31 - 1.
Examples
Example 1
Input
num = "1101111"
Output
[11,0,11,11]
11, 0, 11, 11 satisfies f[i]=f[i-1]+f[i-2].
Example 2
Input
num = "112358130"
Output
[]
No valid split into a Fibonacci-like sequence.