Split Array into Fibonacci Sequence

Description

Given a string S of digits, such as S = "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] <= 2^31 - 1, (that is, each integer fits 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.

Also, 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 S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

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

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

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

Note:

1. 1 <= S.length <= 200
2. S contains only digits.

Solution(javascript)

/*
 * @lc app=leetcode id=842 lang=javascript
 *
 * [842] Split Array into Fibonacci Sequence
 */

// @lc code=start
/**
 * @param {string} S
 * @return {number[]}
 */
const splitIntoFibonacci = function (S) {
  const max = (2 ** 31) - 1
  let result = []
  const inValid = x => (x.length >= 2 && x[0] === '0') || (parseInt(x, 10) < 0) || (parseInt(x, 10) > max)
  const aux = (index, acc = []) => {
    if (index > S.length - 1) {
      if (acc.length >= 3) {
        result = acc
      }
      return
    }
    const { length } = acc
    const a = acc[length - 2]
    const b = acc[length - 1]
    if (inValid(a) || inValid(b)) {
      return
    }
    let current = ''
    for (let i = index; i < S.length; i++) {
      current += S[i]
      const num = parseInt(current, 10)
      if (!inValid(current) && num === Number(a) + Number(b)) {
        aux(i + 1, [...acc, num])
      }
    }
  }
  for (let i = 0; i < S.length; i++) {
    for (let j = i + 1; j < S.length; j++) {
      aux(
        j + 1,
        [S.slice(0, i + 1), S.slice(i + 1, j + 1)],
      )
    }
  }
  return result.map(x => Number(x))
}