Split Array Into Fibonacci Sequence - Leetcode Solution

Problem statement: Given a string num of digits, such as num = "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:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2. Also, 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.

Solution: We will use a backtracking algorithm to find the Fibonacci-like sequence. We will start by choosing the first two numbers of the sequence, the third number will be the sum of the first two numbers and we will check if it is present in the string. If it is present, we will continue the process for the remaining string. If we reach the end of the string and the last number of the sequence is the same as the last number of the string, we have found a valid sequence. If we are unable to find a valid sequence, we backtrack by choosing different combinations of the first two numbers and try again. We will also check if the current substring is starting with a zero, if yes then it is not a valid substring as we cannot have leading zeroes in the middle of the sequence.

Python code:

class Solution: def splitIntoFibonacci(self, num: str) -> List[int]: res = [] self.helper(num, res, 0) return res

def helper(self, num, res, start):
    if start == len(num) and len(res) > 2:
        return True

    for i in range(start, len(num)):
        if num[start] == '0' and i > start:
            break

        val = int(num[start:i + 1])

        if val > 2 ** 31 - 1:
            break

        if len(res) < 2 or val == res[-2] + res[-1]:
            res.append(val)

            if self.helper(num, res, i + 1):
                return True

            res.pop()

    return False

Time Complexity: O(n^2), as we have nested loops to explore all the possible combinations of the first two numbers.

Space Complexity: O(n), as we are storing the Fibonacci sequence in the result array.

1