#842

Split Array into Fibonacci Sequence

expert · 1030 · lc medium +32 · verified · 40.2% accepted · 1,180 likes · top 20%

Description

You are given a digit string num such as "123456579". You want to partition it into a Fibonacci-like sequence, for example [123, 456, 579].

Formally, a Fibonacci-like sequence is a list f of non-negative integers satisfying:

- 0 <= f[i] < 2³¹ (each value fits in a 32-bit signed integer),

- f.length >= 3, and

- f[i] + f[i + 1] == f[i + 2] for all 0 <= i < f.length - 2.

Pieces must not have leading zeros, except for the single digit 0 itself.

Return any valid Fibonacci-like partition of num, or [] if none exists.

Example 1:

Input: num = "1101111"

Output: [11,0,11,11]

Explanation: The output [110, 1, 111] would also be accepted.

Example 2:

Input: num = "112358130"

Output: []

Explanation: The task is impossible.

Example 3:

Input: num = "0123"

Output: []

Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Code

1

2

3

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]: