306. 累加数

🟠   🔖  字符串 回溯  🔗 力扣 LeetCode

题目

An additive number is a string whose digits can form an additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits, return true if it is an additive number or false otherwise.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"

Output: true

Explanation:

The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"

Output: true

Explanation:

The additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Constraints:

• 1 <= num.length <= 35
• num consists only of digits.

Follow up: How would you handle overflow for very large input integers?

题目大意

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须至少 包含 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 <= 35
• num 仅由数字（0 - 9）组成

进阶： 你计划如何处理由过大的整数输入导致的溢出?

解题思路

思路一：回溯法

1. 定义一个数组 track，存储当前选取的累加数序列。
2. 从字符串的起始位置 start 开始递归：
   • 终止条件：当字符串遍历完且累加数序列长度 ≥ 3 时，返回 true。
   • 枚举从 start 到 num.length 的所有子串：
     1. 如果子串有前导零且长度大于 1，则跳过。
     2. 将子串转换为数字 next，判断是否满足累加数性质：
        • 如果满足，将其加入 track 并递归。
        • 如果递归成功，则直接返回 true。
        • 否则，回溯，移除当前数字。
   • 剪枝优化：如果当前子串的值不等于前两个数字之和，直接跳过当前分割。
3. 如果所有分割均不满足条件，返回 false。

复杂度分析

• 时间复杂度：O(2^n)，每个字符都有两种选择（加入当前数字或不加入）。
• 空间复杂度：O(n)，递归栈和存储路径的数组。

---

思路二：迭代法

1. 使用两层循环枚举前两个数字的分割位置，确定初始的两个累加数：
   • 第一层循环确定第一个数字的长度。
   • 第二层循环确定第二个数字的长度。
2. 从第三个数字开始，逐步验证剩余部分是否满足累加数性质。
3. 验证过程：
   • 初始化两个累加数 first 和 second。
   • 从剩余字符串中逐个匹配累加和：
     • 如果匹配成功，则更新累加数，继续验证下一个数字。
     • 如果不匹配，立即终止当前分割。
4. 如果某种分割方式成功匹配完整个字符串，则返回 true；否则，返回 false。

复杂度分析

• 时间复杂度：O(2^n)，两层循环枚举所有可能的分割点。
• 空间复杂度：O(1)，无需额外的递归栈或路径存储。

代码

回溯法

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function (num) {
	let track = [];

	const backtrack = (start) => {
		if (start === num.length && track.length >= 3) return true;

		for (let i = start; i < num.length; i++) {
			if (num[start] === '0' && i > start) break; // 前导零
			const next = Number(num.slice(start, i + 1));

			if (
				track.length >= 2 &&
				track[track.length - 1] + track[track.length - 2] !== next
			) {
				continue;
			}

			track.push(next);
			if (backtrack(i + 1)) return true;
			track.pop();
		}
		return false;
	};

	return backtrack(0);
};

迭代法

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function (num) {
	const n = num.length;

	const isValid = (first, second, start) => {
		while (start < n) {
			const sum = first + second;
			const sumStr = sum.toString();

			// 如果剩余的字符串不以 sumStr 开头，直接返回 false
			if (!num.startsWith(sumStr, start)) return false;

			// 移动到下一段
			start += sumStr.length;

			// 更新 first 和 second
			[first, second] = [second, sum];
		}
		return true;
	};

	for (let i = 1; i < n; i++) {
		if (i > 1 && num[0] === '0') break; // 第一个数字不能有前导零
		const first = Number(num.slice(0, i));

		for (let j = i + 1; j < n; j++) {
			if (j > i + 1 && num[i] === '0') break; // 第二个数字不能有前导零
			const second = Number(num.slice(i, j));

			// 检查从 j 开始的序列是否满足累加数性质
			if (isValid(first, second, j)) return true;
		}
	}

	return false;
};

相关题目

题号	标题	题解	标签	难度	力扣
842	将数组拆分成斐波那契序列		字符串 回溯	🟠	🀄️ 🔗