#842

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Split Array into Fibonacci Sequence

This problem challenges you to split a string into a Fibonacci-like sequence using backtracking and pruning.

Problem Statement

You are given a string of digits, num. Your task is to split the string into a Fibonacci-like sequence, where each number in the sequence is the sum of the two preceding ones.

A valid Fibonacci-like sequence must adhere to the following conditions: each number is non-negative, there are no leading zeroes unless the number is exactly zero, and the sequence must follow the Fibonacci property.

Examples

Example 1

Input: num = "1101111"

Output: [11,0,11,11]

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

Example 2

Input: num = "112358130"

Output: []

The task is impossible.

Example 3

Input: num = "0123"

Output: []

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

Constraints

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

Solution Approach

Backtracking Search

Start by exploring all possible pairs of the first two numbers. For each pair, attempt to build the sequence by checking if the sum of the two numbers matches the next number in the string. Use recursion to explore further, pruning invalid paths early to reduce the search space.

Pruning Invalid Paths

Prune paths where the sum of the two numbers does not match the next number in the sequence. Additionally, avoid paths that start with invalid numbers, like those with leading zeros. This step reduces unnecessary computations and improves the efficiency of the backtracking approach.

Edge Case Handling

Ensure that you handle edge cases such as when there are leading zeroes in the sequence or when it's impossible to split the string into a valid Fibonacci-like sequence. In such cases, return an empty list.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(N)

The time complexity is O(N^2) due to the need to check each possible pair of the first two numbers and recursively build the sequence. The space complexity is O(N) as we store the numbers during backtracking.

What Interviewers Usually Probe

Can the candidate efficiently prune invalid paths without exploring every possibility?
Does the candidate handle edge cases, such as invalid numbers with leading zeros, correctly?
Can the candidate explain the backtracking approach and its pruning mechanism in detail?

Common Pitfalls or Variants

Common pitfalls

Not handling the case where the sequence contains leading zeroes.
Overlooking cases where it's impossible to form a valid sequence, leading to an infinite search.
Not efficiently pruning invalid paths, causing unnecessary recursive calls.

Follow-up variants

What if the string is extremely long? Consider optimizations for larger input sizes.
What if the Fibonacci-like sequence can contain numbers with more than one digit?
Can you extend the problem to include larger numbers beyond typical integer ranges?

FAQ

How do I approach solving the Split Array into Fibonacci Sequence problem?

Start by using backtracking to explore all possible splits. Prune invalid paths where the sum of the last two numbers doesn't match the next part of the sequence.

What is the time complexity of the solution?

The time complexity is O(N^2), as each potential pair of the first two numbers is checked and the sequence is built recursively.

What should I do when I encounter a leading zero in a number?

Avoid numbers that start with leading zeroes, unless the number is exactly zero. This is a common constraint in string-based number problems.

Can this problem be solved with a dynamic programming approach?

While backtracking is the most intuitive approach, dynamic programming could be used if you need to store previously computed sums, but it may not be as efficient in this case.

How does pruning help in solving this problem?

Pruning helps by cutting off invalid paths early in the recursion, preventing unnecessary checks and reducing the overall complexity of the solution.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        def dfs(i):
            if i == n:
                return len(ans) > 2
            x = 0
            for j in range(i, n):
                if j > i and num[i] == '0':
                    break
                x = x * 10 + int(num[j])
                if x > 2**31 - 1 or (len(ans) > 2 and x > ans[-2] + ans[-1]):
                    break
                if len(ans) < 2 or ans[-2] + ans[-1] == x:
                    ans.append(x)
                    if dfs(j + 1):
                        return True
                    ans.pop()
            return False

        n = len(num)
        ans = []
        dfs(0)
        return ans

Continue Practicing

#816 ambiguous coordinates #784 letter case permutation #949 largest time for given digits