题目描述
思路解析动画文字版
记牢这套「定种子 → 后续被和锁死 → 拼不出就回溯」,下面每一帧都在套它。
先把整串 1101111 摆出来,一共 7 位。我们要把它切成一段段数字,让它满足斐波那契规则。先从最左边、最短的种子开始试。
先定第一个种子。从下标 0 取最短的一位,第一个数 = 1。绿色标的就是当前正在用的这一段。
再定第二个种子,取下标 1 的 1,第二个数 = 1。两个种子定下来是 [1, 1],蓝色是已经定死的段。接下来每个数都被它俩锁死了。
第三个数的目标 = 前两数之和 = 1 加 1 = 2。从下标 2 往后拼,先看下标 2 是 0。
下标 2 单独是 0,0 不等于 2;想再往右拼成 01 又犯了前导零,不允许。这个位置怎么都凑不出 2,失败。
回溯。第二个数取 1 走不通,把它撤掉,退回只有第一个数 1 的状态,改让第二个数拉长一点试试。
第二个数改成取下标 1 到 2 的 10,第二个数 = 10。两个种子变成 [1, 10],重新往后推。
第三个数目标 = 1 加 10 = 11。从下标 3 往后拼,先看下标 3 是 1。
单独一个 1 才 1,比目标 11 小,不够。那就把这一段往右多拼一位,看下标 3 到 4。
下标 3 到 4 拼出 11,正好等于目标 11,命中!收进序列,现在是 [1, 10, 11]。继续往后推下一个数。
下一个目标 = 10 加 11 = 21。可剩下只有下标 5、6 这两位,最多拼成 11,离 21 差得远。
一直拼到字符串末尾,最大也只有 11,凑不出 21,这条路又断了。第一个数取 1 时,第二个数取 1、取 10 这两条分支都走死了;其余更长的第二个种子(101、1011…),要么拼出的数超过目标仍不命中,要么剩余位数不足,同样失败,这里折叠展示。所以第一个数取 1 的各种走法确实试遍了,仍不行。
大回溯。第一个数定成 1 的所有分支都走死了,把它也撤掉,改用更长的第一个数重新开局。
第一个数改成取下标 0 到 1 的 11,第一个数 = 11。重新来定第二个种子。
第二个数取下标 2 的 0。注意单独一个 0 是允许的,只有像 01 那样 0 打头才算前导零。两个种子定为 [11, 0]。
第三个数目标 = 11 加 0 = 11。从下标 3 往后拼,先看下标 3 是 1。
单独的 1 比 11 小,不够,把这段往右拼一位,看下标 3 到 4。
下标 3 到 4 拼出 11,等于目标 11,命中!序列变成 [11, 0, 11]。继续往后推。
再下一个目标 = 0 加 11 = 11。从下标 5 往后拼,下标 5 是 1,偏小。
把这段拼到下标 5 到 6,得到 11,又一次正好命中目标 11!序列变成 [11, 0, 11, 11]。
下标正好用到字符串末尾,序列有 4 个数,满足至少 3 个、且每个都是前两数之和。拆分成功,答案 [11, 0, 11, 11]。
回放一遍:11 加 0 等于第三个 11,0 加第三个 11 等于第四个 11,每一步都对得上,这就是一条合法的斐波那契式拆分。
边界先想清:全 0 可拆、标准斐波那契顺着走、以及拆不出时返回空。
两个高频追问:为何用回溯、以及种子的枚举量级,核心都落在「自由度只在前两数」。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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复杂度
- 时间：O(n³)，保守上界 O(n³):枚举前两个种子各 O(n)、每条链线性校验 O(n);本题数字不超过 int32,种子长度至多 10 位,剪枝后实际尝试远少
- 空间：O(n)，递归深度与已选序列长度都是 O(n) 量级
易错点
面试追问把动画讲成自己的话
追问为什么这题不能用普通 DP,而要回溯?
追问前两个数最多枚举多少种?会不会爆?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
给定数字能组成的最大时间
LeetCode 949 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题