LeetCode 题解工作台
累加数
累加数 是一个字符串，组成它的数字可以形成累加序列。 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
class Solution: def isAdditiveNumber(self, num: str) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1：
输入："112358"输出：true 解释：累加序列为:1, 1, 2, 3, 5, 8。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2：
输入："199100199"输出：true 解释：累加序列为:1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
提示：
1 <= num.length <= 35num仅由数字（0-9）组成
进阶：你计划如何处理由过大的整数输入导致的溢出?
解题思路
方法一
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
def dfs(a, b, num):
if not num:
return True
if a + b > 0 and num[0] == '0':
return False
for i in range(1, len(num) + 1):
if a + b == int(num[:i]):
if dfs(b, a + b, num[i:]):
return True
return False
n = len(num)
for i in range(1, n - 1):
for j in range(i + 1, n):
if i > 1 and num[0] == '0':
break
if j - i > 1 and num[i] == '0':
continue
if dfs(int(num[:i]), int(num[i:j]), num[j:]):
return True
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They want you to notice that after picking the first two numbers, the rest of Additive Number is forced rather than freely partitioned.
- question_mark
They are checking whether you catch the leading-zero rule for both starting numbers and later generated values.
- question_mark
They expect pruning logic, not brute-force partition generation across the whole string.
常见陷阱
外企场景- error
Allowing values like "01" or "00" as multi-digit tokens, which makes invalid branches look valid.
- error
Using 32-bit or 64-bit arithmetic blindly, which can break Additive Number on longer substrings near the length limit.
- error
Continuing search after the expected sum fails to match the next substring, instead of pruning that branch immediately.
进阶变体
外企场景- arrow_right_alt
Return the actual additive sequence instead of a boolean, which means storing the chosen numbers along the successful path.
- arrow_right_alt
Count how many valid additive decompositions exist, which removes the early exit and makes pruning even more important.
- arrow_right_alt
Implement the same Additive Number logic with manual string addition to avoid overflow-dependent solutions.