LeetCode 842: Split Array into Fibonacci Sequence Solution

Master LeetCode problem 842 (Split Array into Fibonacci Sequence), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

842. Split Array into Fibonacci Sequence

Medium

String Backtracking

Problem Explanation

Explanation:

To solve this problem, we can use a backtracking approach to recursively try out different combinations of numbers to form the Fibonacci-like sequence. We start by choosing the first two numbers, then recursively check if the next number in the sequence can be formed from the sum of the previous two numbers. If we reach the end of the input string and have a valid Fibonacci-like sequence, we return it.

We iterate through different combinations of the first two numbers.
For each pair of numbers, we try to build the Fibonacci-like sequence.
We check if the next number in the sequence can be formed from the sum of the previous two numbers.
Recursively continue this process until we reach the end of the input string.
If a valid Fibonacci-like sequence is found, return it. Otherwise, return an empty list.

Time Complexity: O(2^N), where N is the length of the input string num. In the worst-case scenario, we explore all possible combinations of numbers.

Space Complexity: O(N), where N is the length of the input string num. The space is used for the recursion stack.

Solution Code

class Solution {
    public List<Integer> splitIntoFibonacci(String num) {
        List<Integer> res = new ArrayList<>();
        backtrack(num, res, 0);
        return res;
    }

    private boolean backtrack(String num, List<Integer> res, int index) {
        if (index == num.length() && res.size() >= 3) {
            return true;
        }
        
        for (int i = index; i < num.length(); i++) {
            if (num.charAt(index) == '0' && i > index) {
                break;
            }
            long curr = Long.parseLong(num.substring(index, i + 1));
            if (curr > Integer.MAX_VALUE) {
                break;
            }
            int size = res.size();
            if (size >= 2 && curr > res.get(size - 1) + res.get(size - 2)) {
                break;
            }
            if (size <= 1 || curr == res.get(size - 1) + res.get(size - 2)) {
                res.add((int) curr);
                if (backtrack(num, res, i + 1)) {
                    return true;
                }
                res.remove(res.size() - 1);
            }
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 842 (Split Array into Fibonacci Sequence)?

This page provides optimized solutions for LeetCode problem 842 (Split Array into Fibonacci Sequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 842 (Split Array into Fibonacci Sequence)?

The time complexity for LeetCode 842 (Split Array into Fibonacci Sequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 842 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 842 in Java, C++, or Python.

Back to LeetCode Solutions