难度：★★★☆☆
类型：字符串
方法：回溯法
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定一个数字字符串 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 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：
输入："123456579"
输出：[123,456,579]
示例 2：
输入: "11235813"
输出: [1,1,2,3,5,8,13]
示例 3：
输入: "112358130"
输出: []
解释: 这项任务无法完成。
示例 4：
输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
示例 5：
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
提示：
1 <= S.length <= 200
字符串 S 中只含有数字。
通过次数25,109提交次数50,854
解答
这是回溯算法的一道经典题，回溯法的思想在于，对于纷繁复杂的限定规则和广袤无垠的搜索空间，通过一种递归迭代的思想去逐步求解，在递归过程中
，需要设置尽可能多的跳出条件，用以缩小搜查范围。回溯算法的重难点在于递归函数的构建，好在套路是差不多的。
我们首先定义一个列表ans，如果成功的话，用于存储搜查结果。
定义一个回溯函数backtrack，该函数的输入是一个下标数字，范围是从0到len(S)-1，输出是一个布尔量，代表的是S[index:]子串能否成功拆分并添加到结果列表ans内，使得ans中呈现斐波那契排布。
回溯函数有以下几个套路：
【函数开头给出终止条件】在函数开始，就要判断输入index是否已经超过了S的范围，也就是index==len(S)，如果是，说明整个S串的判断已经结束了，但这并不能说明整个子串可以被拆分为斐波那契，例如[1,2]不是斐波那契数列，需要根据ans列表中的数字数量是否达到了3个来判别。
【函数前半部分增加筛选条件进行搜索空间的剪枝】由于我们并不知道数组中每个数字是多少位的，需要从1开始逐个增加，我们从index开始，一直到len(S)-1的数字i，对于从当前头部切下来的子串S[index:i+1]，我们记录为cur变量，有以下几个地方可以考虑剪枝：
-
开头是零的数字是不被允许的，例如“01”，但是要注意，“0”是被允许的，因为它只有一位。
-
如果cur变量过大，也是不必继续的，i增加到什么时候就没有必要再研究index开头的子串了呢，题目中给出了范围的限制，也就是当前数字达到2的31次-1时停止，就没有必要在往后了。
-
如果当前数字cur已经超过了ans列表中末尾两个元素的和，也没必要继续要就index开头的子串了。
只要不是以上情况，就可以针对index开头的子串进行研究，需要研究哪些方面呢？尤其要判断当前数字cur是否是ans列表末尾两个数字的和，如果是，则预先将cur添加到ans中，从i+1位置开始回溯，如果回溯失败，则将刚刚添加到ans中的元素弹出，继续下一轮循环，增加i。
这里要注意ans列表中元素个数小于3的情况，可以直接添加当前数字cur。
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
ans = list()
def backtrack(index: int):
if index == len(S):
return len(ans) >= 3
curr = 0
for i in range(index, len(S)):
if i != index and S[index] == "0":
break
curr = curr * 10 + int(S[i])
if curr > 2 ** 31 - 1:
break
if len(ans) >= 2 and curr > ans[-2] + ans[-1]:
break
if len(ans) < 2 or curr == ans[-2] + ans[-1]:
ans.append(curr)
if backtrack(i + 1):
return True
ans.pop()
return False
backtrack(0)
return ans
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论