842.将数组拆分成斐波那契序列

链接：842.将数组拆分成斐波那契序列
难度：Medium
标签：字符串、回溯
简介：给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。

题解 1 - typescript

• 编辑时间：2020-12-08
• 执行用时：104ms
• 内存消耗：40.8MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/solution/jiang-shu-zu-chai-fen-cheng-fei-bo-na-qi-ts6c/)。

function splitIntoFibonacci(S: string): number[] {
  const list = [];
  const maxNum = Math.pow(2, 31) - 1;
  const len = S.length;
  const numS = S.split('').map(v => +v);
  (function backtrack(index = 0, sum = 0, prev = 0) {
    if (index === len) return list.length >= 3;
    let curLong = 0;
    for (let i = index; i < len; i++) {
      if (i > index && numS[index] === 0) break;
      curLong = curLong * 10 + numS[i];
      if (curLong > maxNum) break;
      if (list.length >= 2) {
        if (curLong < sum) continue;
        else if (curLong > sum) break;
      }
      list.push(curLong);
      if (backtrack(i + 1, prev + curLong, curLong)) return true;
      list.pop();
    }
    return false;
  })();
  return list;
}