共计 2340 个字符，预计需要花费 6 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 306. 累加数 ，难度为 中等。
Tag :「回溯算法」、「高精度」
累加数 是一个字符串，组成它的数字能够造成累加序列。
一个无效的 累加序列 必须 至多 蕴含 3 个数。除了最开始的两个数以外，字符串中的其余数都等于它之前两个数相加的和。
给你一个只蕴含数字 '0'-'9' 的字符串，编写一个算法来判断给定输出是否是 累加数。如果是，返回 true；否则，返回 false。
阐明：累加序列里的数 不会 以 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）组成
进阶：你打算如何解决由过大的整数输出导致的溢出?
回溯 + 高精度加法
给定的 $nums$ 的长度只有 $35$，且要求序列的第三个数开始由前两个数相加而来。
容易想到通过 DFS 爆搜每个数的宰割点，同时利用累加数的个性（第三个数起，每个数均由为前两数之和）进行剪枝。
具体的，咱们能够实现一个 boolean dfs(int u) 函数，入参为以后决策到 $num$ 的哪一位，返回值为决策后果（序列）是否为累加数序列，爆搜过程中的宰割数序列寄存到 $list$ 中。
因为是 从地位 $u$ 作为开始地位决策如何宰割出以后数 $x$，咱们能够枚举以后数的完结地位，范畴为 $[u, n – 1]$，但须要留神宰割数不能蕴含前导零，即如果 $num[u] = 0$，则以后数只能为 $0$。
同时，一个非法的宰割数必然满足「其值大小为前两数之和」，因而以后数 $x$ 可能被增加到 $list$ 的充要条件为：
- $list$ 长度有余 $2$，即 $x$ 为序列中的前两数，不存在值大小的束缚问题，$x$ 能够被间接到 $list$ 并持续爆搜；
- $list$ 长度大于等于 $2$，即 $x$ 须要满足「其值大小为前两数之和」要求，以此条件作为剪枝，满足要求的 $x$ 能力追加到 $list$ 中并持续爆搜。
最初，在整个 DFS 过程中咱们须要监测「以后数」与「前两数之和」是否相等，而宰割数长度最大为 $35$，存在溢出危险，咱们须要实现「高精度加法」，实现一个 check 函数，用于查看 a + b 是否为 c，其中 a、b 和 c 均为应用「逆序」存储数值的数组（最高位对应个位，举个 🌰，$a = 35$，则有 [5, 3]）。
若爆搜过程能顺利完结（失去长度至多为 $3$ 的序列），则阐明可能拆分出累加数序列，返回 True，否则返回 False。
至此，咱们解决了本题，并通过引入「高精度」来答复了「进阶」局部的问题。
代码：
class Solution {
String num;
int n;
List<List<Integer>> list = new ArrayList<>();
public boolean isAdditiveNumber(String _num) {
num = _num;
n = num.length();
return dfs(0);
}
boolean dfs(int u) {int m = list.size();
if (u == n) return m >= 3;
int max = num.charAt(u) == '0' ? u + 1 : n;
List<Integer> cur = new ArrayList<>();
for (int i = u; i < max; i++) {cur.add(0, num.charAt(i) - '0');
if (m < 2 || check(list.get(m - 2), list.get(m - 1), cur)) {list.add(cur);
if (dfs(i + 1)) return true;
list.remove(list.size() - 1);
}
}
return false;
}
boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {List<Integer> ans = new ArrayList<>();
int t = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {if (i < a.size()) t += a.get(i);
if (i < b.size()) t += b.get(i);
ans.add(t % 10);
t /= 10;
}
if (t > 0) ans.add(t);
boolean ok = c.size() == ans.size();
for (int i = 0; i < c.size() && ok; i++) {if (c.get(i) != ans.get(i)) ok = false;
}
return ok;
}
}- 工夫复杂度：爆搜的复杂度为指数级别，且存在剪枝操作，剖析时空复杂度意义不大
- 空间复杂度：爆搜的复杂度为指数级别，且存在剪枝操作，剖析时空复杂度意义不大
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.306 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
