Split Array into Fibonacci Sequence

medium backtracking string

Problem

Given a string of digits, return any split of length >= 3 such that each value (no leading zeros, fits in 32-bit int) equals the sum of the previous two. Return [] if impossible.

Inputnum = "1101111"

Output[11,0,11,11]

One valid split where each number = sum of previous two.

input

def splitIntoFibonacci(num):
    n = len(num)
    res = []
    def backtrack(start, path):
        if start == n and len(path) >= 3:
            res.extend(path); return True
        for end in range(start + 1, n + 1):
            piece = num[start:end]
            if len(piece) > 1 and piece[0] == "0": break
            val = int(piece)
            if val > 2**31 - 1: break
            if len(path) < 2 or path[-1] + path[-2] == val:
                if backtrack(end, path + [val]): return True
        return False
    backtrack(0, [])
    return res

function splitIntoFibonacci(num) {
  const n = num.length;
  const res = [];
  const backtrack = (start, path) => {
    if (start === n && path.length >= 3) { res.push(...path); return true; }
    for (let end = start + 1; end <= n; end++) {
      const piece = num.slice(start, end);
      if (piece.length > 1 && piece[0] === "0") break;
      const val = Number(piece);
      if (val > 2147483647) break;
      if (path.length < 2 || path[path.length - 1] + path[path.length - 2] === val) {
        path.push(val);
        if (backtrack(end, path)) return true;
        path.pop();
      }
    }
    return false;
  };
  backtrack(0, []);
  return res;
}

import java.util.*;
class Solution {
  public List<Integer> splitIntoFibonacci(String num) {
    List<Integer> res = new ArrayList<>();
    backtrack(num, 0, res);
    return res;
  }
  boolean backtrack(String num, int start, List<Integer> path) {
    if (start == num.length() && path.size() >= 3) return true;
    for (int end = start + 1; end <= num.length(); end++) {
      String piece = num.substring(start, end);
      if (piece.length() > 1 && piece.charAt(0) == '0') break;
      long val = Long.parseLong(piece);
      if (val > Integer.MAX_VALUE) break;
      int s = path.size();
      if (s < 2 || path.get(s - 1) + path.get(s - 2) == val) {
        path.add((int) val);
        if (backtrack(num, end, path)) return true;
        path.remove(path.size() - 1);
      }
    }
    return false;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool backtrack(const string &num, int start, vector<int> &path) {
        if (start == (int)num.size() && path.size() >= 3) return true;
        for (int end = start + 1; end <= (int)num.size(); end++) {
            string piece = num.substr(start, end - start);
            if (piece.size() > 1 && piece[0] == '0') break;
            long long val = stoll(piece);
            if (val > INT_MAX) break;
            int s = path.size();
            if (s < 2 || (long long)path[s - 1] + path[s - 2] == val) {
                path.push_back((int)val);
                if (backtrack(num, end, path)) return true;
                path.pop_back();
            }
        }
        return false;
    }
    vector<int> splitIntoFibonacci(string num) {
        vector<int> res;
        backtrack(num, 0, res);
        return res;
    }
};

Explanation

We are handed a string of digits and must cut it into numbers where every number equals the sum of the previous two, just like a Fibonacci sequence. We find one valid split using backtracking.

backtrack(start, path) tries every possible next number by extending the cut point end from start forward. Each candidate piece is checked: it cannot have a leading zero (unless it is just "0") and cannot exceed a 32-bit integer — both conditions break the loop early since longer pieces only get bigger.

The Fibonacci rule lives in path[-1] + path[-2] == val. While we have fewer than two numbers we are free to pick anything (we are seeding the sequence); after that, a candidate is only accepted if it equals the sum of the last two. If accepted, we add it to path and recurse.

We have a winner when we reach the end of the string with at least 3 numbers. The function returns True and unwinds. If no split works, it returns an empty list.

Example: num = "1101111". The split [11, 0, 11, 11] works because 11 + 0 = 11 and 0 + 11 = 11 — each value is the sum of the two before it.

Time: O(n^3) worst case Space: O(n)