842. Split Array into Fibonacci Sequence LeetCode Solution

In this guide, you will get 842. Split Array into Fibonacci Sequence LeetCode Solution with the best time and space complexity. The solution to Split Array into Fibonacci Sequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Split Array into Fibonacci Sequence solution in C++
Split Array into Fibonacci Sequence solution in Java
Split Array into Fibonacci Sequence solution in Python
Additional Resources

842. Split Array into Fibonacci Sequence LeetCode Solution image

Problem Statement of Split Array into Fibonacci Sequence

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:

0 <= f[i] = 3, and
f[i] + f[i + 1] == f[i + 2] for all 0 <= i < f.length – 2.

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.

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.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity:

842. Split Array into Fibonacci Sequence LeetCode Solution in C++

class Solution {
 public:
  vector<int> splitIntoFibonacci(string num) {
    vector<int> ans;
    dfs(num, 0, ans);
    return ans;
  }

 private:
  bool dfs(const string& num, int s, vector<int>& ans) {
    if (s == num.length() && ans.size() >= 3)
      return true;

    for (int i = s; i < num.length(); ++i) {
      if (num[s] == '0' && i > s)
        break;
      const long val = stol(num.substr(s, i + 1 - s));
      if (val > INT_MAX)
        break;
      if (ans.size() >= 2 &&
          val > ans[ans.size() - 2] + static_cast<long>(ans.back()))
        break;
      if (ans.size() <= 1 ||
          val == ans[ans.size() - 2] + static_cast<long>(ans.back())) {
        ans.push_back(val);
        if (dfs(num, i + 1, ans))
          return true;
        ans.pop_back();
      }
    }

    return false;
  }
};
/* code provided by PROGIEZ */

842. Split Array into Fibonacci Sequence LeetCode Solution in Java

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

  private boolean dfs(final String num, int s, List<Integer> ans) {
    if (s == num.length() && ans.size() >= 3)
      return true;

    for (int i = s; i < num.length(); ++i) {
      if (num.charAt(s) == '0' && i > s)
        break;
      final long val = Long.valueOf(num.substring(s, i + 1));
      if (val > Integer.MAX_VALUE)
        break;
      if (ans.size() >= 2 && val > ans.get(ans.size() - 2) + ans.get(ans.size() - 1))
        break;
      if (ans.size() <= 1 || val == ans.get(ans.size() - 2) + ans.get(ans.size() - 1)) {
        ans.add((int) val);
        if (dfs(num, i + 1, ans))
          return true;
        ans.remove(ans.size() - 1);
      }
    }

    return false;
  }
}
// code provided by PROGIEZ