0842. Split Array into Fibonacci Sequence

题目信息

题号:

0842

难度:

Medium

主题:

数字字符串、序列拆分、斐波那契关系

原题:

LeetCode 0842

重点:

必须使用全部数字并拆出至少三个 32 位非负整数;除数字 0 外不能有前导零,后续每项等于前两项之和

题目重述

给定只含数字的字符串 num。在数字之间加入分隔位置,把整个字符串按原顺序拆成一个整数序列,要求:

  • 序列至少包含三个数,并且所有数字字符都被恰好使用一次;

  • 每个数位于 [0, 2^31 - 1] 范围内;

  • 除单独的 0 外,任何数都不能以 0 开头;

  • 从第三项开始,每个数都等于前两项之和。

若存在合法拆分,返回任意一个满足条件的序列;若不存在,返回空数组。多个合法答案无需按特定顺序选择。

1 <= num.length <= 200。

自建示例

序列中允许出现单独的零:

输入:num = "1011"
输出:[1,0,1,1]
解释:1 + 0 = 1,0 + 1 = 1,四段使用了全部数字,且单独的 0 不违反前导零规则。

无法使用全部数字:

输入:num = "1234"
输出:[]
解释:不存在把全部四个数字拆成至少三项且持续满足前两项之和的方式。