Problem

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, 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.

Examples

Example 1

1
2
3

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

Example 2

1
2
3

Input: num = "112358130"
Output: []
Explanation: The task is impossible.

Example 3

1
2
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.

Solution

Method 1 – Backtracking

Intuition

Try all possible ways to split the string into numbers, and build the sequence step by step. At each step, check if the next number matches the sum of the previous two. If so, continue; otherwise, backtrack. Handle leading zeros and integer overflow as constraints.

Approach

  1. Use backtracking to try every possible split of the string into numbers.
  2. For each split, check:
    • No number has leading zeros unless it is ‘0’.
    • Each number fits in a 32-bit signed integer.
    • The sequence follows the Fibonacci property: f[i] + f[i+1] == f[i+2].
  3. If a valid sequence of length at least 3 is found, return it.
  4. If no valid sequence exists, return an empty list.

Code

 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 {
public:
    vector<int> splitIntoFibonacci(string num) {
        vector<int> ans;
        dfs(num, 0, ans);
        return ans.size() >= 3 ? ans : vector<int>{};
    }
    bool dfs(const string& s, int idx, vector<int>& ans) {
        if (idx == s.size()) return ans.size() >= 3;
        long long n = 0;
        for (int i = idx; i < s.size(); ++i) {
            if (i > idx && s[idx] == '0') break;
            n = n * 10 + s[i] - '0';
            if (n > INT_MAX) break;
            if (ans.size() < 2 || n == (long long)ans[ans.size()-1] + ans[ans.size()-2]) {
                ans.push_back(n);
                if (dfs(s, i+1, ans)) return true;
                ans.pop_back();
            }
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func splitIntoFibonacci(num string) []int {
    var ans []int
    var dfs func(idx int) bool
    dfs = func(idx int) bool {
        if idx == len(num) {
            return len(ans) >= 3
        }
        n := 0
        for i := idx; i < len(num); i++ {
            if i > idx && num[idx] == '0' {
                break
            }
            n = n*10 + int(num[i]-'0')
            if n > 1<<31-1 {
                break
            }
            if len(ans) < 2 || n == ans[len(ans)-1]+ans[len(ans)-2] {
                ans = append(ans, n)
                if dfs(i+1) {
                    return true
                }
                ans = ans[:len(ans)-1]
            }
        }
        return false
    }
    dfs(0)
    if len(ans) >= 3 {
        return ans
    }
    return []int{}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public List<Integer> splitIntoFibonacci(String num) {
        List<Integer> ans = new ArrayList<>();
        dfs(num, 0, ans);
        return ans.size() >= 3 ? ans : new ArrayList<>();
    }
    boolean dfs(String s, int idx, List<Integer> ans) {
        if (idx == s.length()) return ans.size() >= 3;
        long n = 0;
        for (int i = idx; i < s.length(); ++i) {
            if (i > idx && s.charAt(idx) == '0') break;
            n = n * 10 + s.charAt(i) - '0';
            if (n > Integer.MAX_VALUE) break;
            if (ans.size() < 2 || n == (long)ans.get(ans.size()-1) + ans.get(ans.size()-2)) {
                ans.add((int)n);
                if (dfs(s, i+1, ans)) return true;
                ans.remove(ans.size()-1);
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun splitIntoFibonacci(num: String): List<Int> {
        val ans = mutableListOf<Int>()
        fun dfs(idx: Int): Boolean {
            if (idx == num.length) return ans.size >= 3
            var n = 0L
            for (i in idx until num.length) {
                if (i > idx && num[idx] == '0') break
                n = n * 10 + (num[i] - '0')
                if (n > Int.MAX_VALUE) break
                if (ans.size < 2 || n == ans[ans.size-1].toLong() + ans[ans.size-2].toLong()) {
                    ans.add(n.toInt())
                    if (dfs(i+1)) return true
                    ans.removeAt(ans.size-1)
                }
            }
            return false
        }
        dfs(0)
        return if (ans.size >= 3) ans else emptyList()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def splitIntoFibonacci(num: str) -> list[int]:
    def backtrack(idx: int, ans: list[int]) -> bool:
        if idx == len(num):
            return len(ans) >= 3
        n = 0
        for i in range(idx, len(num)):
            if i > idx and num[idx] == '0':
                break
            n = n * 10 + int(num[i])
            if n > 2**31 - 1:
                break
            if len(ans) < 2 or n == ans[-1] + ans[-2]:
                ans.append(n)
                if backtrack(i+1, ans):
                    return True
                ans.pop()
        return False
    ans = []
    backtrack(0, ans)
    return ans if len(ans) >= 3 else []
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn split_into_fibonacci(num: String) -> Vec<i32> {
        fn dfs(s: &str, idx: usize, ans: &mut Vec<i32>) -> bool {
            if idx == s.len() { return ans.len() >= 3; }
            let mut n: i64 = 0;
            for i in idx..s.len() {
                if i > idx && &s[idx..idx+1] == "0" { break; }
                n = n * 10 + (s[i..i+1].parse::<i64>().unwrap());
                if n > i32::MAX as i64 { break; }
                if ans.len() < 2 || n == ans[ans.len()-1] as i64 + ans[ans.len()-2] as i64 {
                    ans.push(n as i32);
                    if dfs(s, i+1, ans) { return true; }
                    ans.pop();
                }
            }
            false
        }
        let mut ans = Vec::new();
        dfs(&num, 0, &mut ans);
        if ans.len() >= 3 { ans } else { vec![] }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    splitIntoFibonacci(num: string): number[] {
        const ans: number[] = [];
        function dfs(idx: number): boolean {
            if (idx === num.length) return ans.length >= 3;
            let n = 0;
            for (let i = idx; i < num.length; ++i) {
                if (i > idx && num[idx] === '0') break;
                n = n * 10 + Number(num[i]);
                if (n > 2 ** 31 - 1) break;
                if (ans.length < 2 || n === ans[ans.length-1] + ans[ans.length-2]) {
                    ans.push(n);
                    if (dfs(i+1)) return true;
                    ans.pop();
                }
            }
            return false;
        }
        dfs(0);
        return ans.length >= 3 ? ans : [];
    }
}

Complexity

  • ⏰ Time complexity: O(2^n) – Backtracking tries all splits, but prunes invalid ones early.
  • 🧺 Space complexity: O(n) – Space for the answer sequence and recursion stack.