306. 累加数 : 回溯 + 高精度加法 运用题

题目描述

这是 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 <= 351<=num.length<=35
• num 仅由数字（0 - 9）组成

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

回溯 + 高精度加法

给定的 numsnums 的长度只有 3535，且要求序列的第三个数开始由前两个数相加而来。

容易想到通过 DFS 爆搜每个数的分割点，同时利用累加数的特性（第三个数起，每个数均由为前两数之和）进行剪枝。

具体的，我们可以实现一个 boolean dfs(int u) 函数，入参为当前决策到 numnum 的哪一位，返回值为决策结果（序列）是否为累加数序列，爆搜过程中的分割数序列存放到 listlist 中。

由于是 从位置 uu 作为开始位置决策如何分割出当前数 xx，我们可以枚举当前数的结束位置，范围为 [u, n - 1][u,n−1]，但需要注意分割数不能包含前导零，即如果 num[u] = 0num[u]=0，则当前数只能为 00。

同时，一个合法的分割数必然满足「其值大小为前两数之和」，因此当前数 xx 能够被添加到 listlist 的充要条件为：

1. listlist 长度不足 22，即 xx 为序列中的前两数，不存在值大小的约束问题，xx 可以被直接到 listlist 并继续爆搜；
2. listlist 长度大于等于 22，即 xx 需要满足「其值大小为前两数之和」要求，以此条件作为剪枝，满足要求的 xx 才能追加到 listlist 中并继续爆搜。

最后，在整个 DFS 过程中我们需要监测「当前数」与「前两数之和」是否相等，而分割数长度最大为 3535，存在溢出风险，我们需要实现「高精度加法」，实现一个 check 函数，用于检查 a + b 是否为 c，其中 a、b 和 c 均为使用「逆序」存储数值的数组（最高位对应个位，举个 🌰，a = 35a=35，则有 [5, 3]）。

若爆搜过程能顺利结束（得到长度至少为 33 的序列），则说明能够拆分出累加数序列，返回 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 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。