pythonunpack到数列_842.将数组拆分成斐波那契数列
（Python）
难度：★★★☆☆
类型：字符串
⽅法：回溯法
⼒扣链接请移步本题传送门
更多⼒扣中等题的解决⽅案请移步⼒扣中等题⽬录
给定⼀个数字字符串 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":python 定义数组
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解决⽅案，请移步⼒扣中等题解析

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。