题目

类型：字符串

解题思路

回溯 + 高精度加法

1、通过 DFS 爆搜每个数的分割点，同时利用累加数的特性（第三个数起，每个数均由为前两数之和）进行剪枝。
2、实现一个 boolean dfs(int u)函数，入参为当前决策到 num 的哪一位，返回值为决策结果（序列）是否为累加数序列，爆搜过程中的分割数序列存放到 list 中
3、由于是 从位置 u 作为开始位置决策如何分割出当前数 x，可以枚举当前数的结束位置，范围为 [u, n - 1]，但需要注意分割数不能包含前导零，即如果 num[u] = 0，则当前数只能为 0。
4、一个合法的分割数必然满足「其值大小为前两数之和」，因此当前数 x 能够被添加到 list 的充要条件为

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

5、在整个 DFS 过程中需要监测「当前数」与「前两数之和」是否相等，而分割数长度最大为 35，存在溢出风险，需要实现「高精度加法」，实现一个 check 函数，用于检查 a + b 是否为 c，其中 a、b 和 c 均为使用「逆序」存储数值的数组（最高位对应个位，比如 a = 35，则有 [5, 3]）。
6、若爆搜过程能顺利结束（得到长度至少为 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;
    }
}