How do I approach solving the Split Array into Fibonacci Sequence problem?

Start by using backtracking to explore all possible splits. Prune invalid paths where the sum of the last two numbers doesn't match the next part of the sequence.

What is the time complexity of the solution?

The time complexity is O(N^2), as each potential pair of the first two numbers is checked and the sequence is built recursively.

What should I do when I encounter a leading zero in a number?

Avoid numbers that start with leading zeroes, unless the number is exactly zero. This is a common constraint in string-based number problems.

Can this problem be solved with a dynamic programming approach?

While backtracking is the most intuitive approach, dynamic programming could be used if you need to store previously computed sums, but it may not be as efficient in this case.

How does pruning help in solving this problem?

Pruning helps by cutting off invalid paths early in the recursion, preventing unnecessary checks and reducing the overall complexity of the solution.

#842

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

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

给定一个数字字符串 num ，比如 "123456579" ，我们可以将它分成「斐波那契式」的序列 [123, 456, 579] 。形式上，斐波那契式序列是一个非负整数列表 f ，且满足： 0 31 ，（也就是说，每个整数都符合 32 位有符号整数类型） f.length >= 3 对于所…

字符串回溯

题目描述

给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。

形式上，斐波那契式 序列是一个非负整数列表 f，且满足：

0 <= f[i] < 2³¹ ，（也就是说，每个整数都符合 32 位 有符号整数类型）
f.length >= 3
对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。

示例 1：

输入：num = "1101111"
输出：[11,0,11,11]
解释：输出 [110,1,111] 也可以。

示例 2：

输入: num = "112358130"
输出: []
解释: 无法拆分。

示例 3：

输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。

提示：

1 <= num.length <= 200
num 中只含有数字

lightbulb

解题思路

方法一：回溯 + 剪枝

我们设计一个函数 $dfs(i)$ ，表示从字符串 $num$ 的第 $i$ 个字符开始拆分，拆分出的斐波那契式序列是否满足题目要求。如果满足，我们就返回 $true$ ，否则返回 $false$ 。

函数 $dfs(i)$ 的具体实现如下：

如果 $i$ 等于字符串 $num$ 的长度，说明我们已经拆分完整个字符串，此时我们只需要判断拆分出的序列的长度是否大于 $2$ 即可。如果大于 $2$ ，说明我们找到了一组满足题目要求的斐波那契式序列，返回 $true$ ；否则返回 $false$ 。

如果 $i$ 小于字符串 $num$ 的长度，我们需要枚举拆分出的第一个数 $x$ ，如果 $x$ 的长度大于 $1$ ，且以 $0$ 开头，说明 $x$ 不是一个合法的数，我们直接返回 $false$ 。否则我们将 $x$ 转换成十进制数，如果 $x$ 大于 $2^{31} - 1$ ，或者 $x$ 大于 $ans$ 的最后两个数之和，直接返回 $false$ 。如果 $ans$ 的长度小于 $2$ ，或者 $x$ 等于 $ans$ 的最后两个数之和，我们将 $x$ 加入到 $ans$ 中，然后继续拆分字符串 $num$ 的后面的部分，如果返回 $true$ ，说明我们找到了一组满足题目要求的斐波那契式序列，返回 $true$ ；否则我们将 $x$ 从 $ans$ 中移除，然后继续枚举拆分出的第一个数 $x$ 。

时间复杂度 $O(n \times \log^2 M)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $M$ 分别是字符串 $num$ 的长度和整型数的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        def dfs(i):
            if i == n:
                return len(ans) > 2
            x = 0
            for j in range(i, n):
                if j > i and num[i] == '0':
                    break
                x = x * 10 + int(num[j])
                if x > 2**31 - 1 or (len(ans) > 2 and x > ans[-2] + ans[-1]):
                    break
                if len(ans) < 2 or ans[-2] + ans[-1] == x:
                    ans.append(x)
                    if dfs(j + 1):
                        return True
                    ans.pop()
            return False

        n = len(num)
        ans = []
        dfs(0)
        return ans

speed

复杂度分析

指标	值
时间	O(N^2)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently prune invalid paths without exploring every possibility?
question_mark
Does the candidate handle edge cases, such as invalid numbers with leading zeros, correctly?
question_mark
Can the candidate explain the backtracking approach and its pruning mechanism in detail?

warning

常见陷阱

外企场景

error
Not handling the case where the sequence contains leading zeroes.
error
Overlooking cases where it's impossible to form a valid sequence, leading to an infinite search.
error
Not efficiently pruning invalid paths, causing unnecessary recursive calls.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string is extremely long? Consider optimizations for larger input sizes.
arrow_right_alt
What if the Fibonacci-like sequence can contain numbers with more than one digit?
arrow_right_alt
Can you extend the problem to include larger numbers beyond typical integer ranges?

help

常见问题

外企场景

继续练习

#816 模糊坐标 #784 字母大小写全排列 #949 给定数字能组成的最大时间