Leetcode•Nov 18, 2026
Split Array into Fibonacci Sequence
Hazrat Ali
Leetcode
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] < 231, (that is, each integer fits in a 32-bit signed integer type),f.length >= 3, andf[i] + f[i + 1] == f[i + 2]for all0 <= 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.
Solution
var splitIntoFibonacci = function(num) {
let result = [];
const MAX = 2147483647;
function backtrack(index) {
if (index === num.length) {
return result.length >= 3;
}
let current = 0;
for (let i = index; i < num.length; i++) {
if (i > index && num[index] === '0') {
break;
}
current = current * 10 + Number(num[i]);
if (current > MAX) {
break;
}
let size = result.length;
if (size >= 2) {
let sum = result[size - 1] + result[size - 2];
if (current < sum) {
continue;
}
if (current > sum) {
break;
}
}
result.push(current);
if (backtrack(i + 1)) {
return true;
}
result.pop();
}
return false;
}
backtrack(0);
return result.length >= 3 ? result : [];
};