mediumBacktrackingString 0 views

Split Array into Fibonacci Sequence

You are given a string of digits num, such as "123456579".

You are given a string of digits num, such as "123456579". We can split it into a Fibonacci-like sequence [123, 456, 579].

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

Note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from num, or return [] if it cannot be done.

Split Array into Fibonacci Sequence diagram

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.

Constraints

  • 1 <= num.length <= 200
  • num contains only digits.

Hints

No hints yet.

Companies

No companies reported yet.

Discussion

Sign in to join the discussion.

Loading discussion...

Test results

No test cases yet.