# \[842]\[中等]\[DFS] 将数组拆分成斐波那契序列

## 题目描述

[842. 将数组拆分成斐波那契序列](https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/)

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

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

* 0 <= F\[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
* F.length >= 3；
* 对于所有的0 <= i < F.length - 2，都有 F\[i] + F\[i+1] = F\[i+2] 成立。

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

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

## 解题思路

遍历整个字符串, 使用DFS的思路, 逐段截取, 判断是否符合斐波那契序列的条件, 满足则添加到当前序列中, 继续向下遍历; 否则**向上回溯**.

注意:

* 如果当前序列长度小于3, 则遇到数直接添加到序列中, 然后才判断斐波那契序列的条件
* 停止条件是索引越界, 这时说明最后一个字符和组成数字, 被添加到序列中了. 如果此时的序列长度不小于3, 就得到了一个斐波那契式的序列, 返回

本题最重要的是进行**剪枝优化**, 具体剪枝点见代码.

```python
class Solution:
    UPPER = 2 ** 31 - 1

    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        result = []

        def dfs(start, series):
            if start == n:
                if len(series) >= 3:
                    result.append(series)
                    return True  # 找到一个就可以返回, 不必再继续寻找, 应做剪枝
                return

            for i in range(start, n):
                sub = S[start: i + 1]
                if not (sub.startswith('0') and len(sub) > 1):  # 剪枝1, 每个数字块不能以0开头, 单独的0除外
                    number = int(sub)
                    if number > self.UPPER:  # 剪枝2, 如果当前数值过大, 后续的会更大, 不再继续向后搜索
                        break

                    if len(series) >= 2:
                        if number == series[-1] + series[-2]:
                            if dfs(i + 1, series + [number]):  # 剪枝4, 已经找到一个结果, 无需继续查找
                                return True
                        elif number > series[-1] + series[-2]:  # 剪枝3, 当前的数字已经大过期待值, 后续更大, 不再向后搜索
                            break
                    else:  # 还没有凑齐两个数字, 先填至两个数字
                        if dfs(i + 1, series + [number]):  # 剪枝4, 已经找到一个结果, 无需继续查找
                            return True

        dfs(0, [])
        return result[0] if len(result) > 0 else result
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/dfs/842-jiang-shu-zu-chai-fen-cheng-fei-bo-na-qi-xu-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.