# 842. Split Array into Fibonacci Sequence 将数组拆分成斐波那契序列

@TOC

## # 题目描述

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:

1. 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
2. F.length >= 3;
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: []
``````

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.

## # 解题方法

``````输入："539834657215398346785398346991079669377161950407626991734534318677529701785098211336528511"

``````

``````class Solution(object):
def splitIntoFibonacci(self, S):
"""
:type S: str
:rtype: List[int]
"""
res = []
self.dfs(S, [], res)
return res

def dfs(self, num_str, path, res):
if len(path) >= 3 and  path[-1] != path[-2] + path[-3]:
return False
if not num_str and len(path) >= 3:
res.extend(path)
return True
for i in range(len(num_str)):
curr = num_str[:i+1]
if (curr[0] == '0' and len(curr) != 1) or int(curr) >= 2**31:
continue
if self.dfs(num_str[i+1:], path + [int(curr)], res):
return True
return False
``````

``````class Solution {
public:
vector<int> splitIntoFibonacci(string S) {
vector<int> path;
helper(S, path, 0);
return path;
}
// [start, S.size())
bool helper(string& num, vector<int>& path, int start) {
if (start >= num.size() && path.size() >= 3)
return true;
for (int i = 1; start + i <= num.size(); i++) {
if (num[start] == '0' && i > 1) break;
long long subll = stoll(num.substr(start, i));
if (subll > INT_MAX)
return false;
if (path.size() >= 2 && subll > path[path.size() - 1] + path[path.size() - 2])
return false;
if (path.size() <= 1 || subll == path[path.size() - 1] + path[path.size() - 2]) {
path.push_back((int)subll);
if (helper(num, path, start + i)) {
return true;
}
path.pop_back();
}
}
return false;
}
};
``````

## # 日期

2018 年 6 月 12 日 —— 实验室上午放假2333刷题吧 2018 年 12 月 22 日 —— 今天冬至