题解 | #累加序列#

题目要求判断给定的字符串是否为累加数。累加数是指由至少三个数字组成的序列，除了最开始的两个数以外，序列中的每个后续数字都是前两个数字之和。

为了解决这个问题，我们可以使用回溯法。回溯法是一种递归的方法，用于尝试在可能的分支中搜索解。

算法的主要思路如下：

1. 首先检查字符串的长度是否小于3，如果是，则无法构成累加数，返回false。
2. 定义一个辅助函数backtrack，它接受五个参数：输入字符串num、当前索引index、前两个数字num1和num2，以及已经找到的数字个数count。
3. 在backtrack函数中，首先判断当前索引是否达到字符串的长度。如果是，说明已经遍历完整个字符串，那么检查已找到的数字个数count是否大于等于3，如果是，则返回true；否则返回false。
4. 在每一次递归中，我们使用循环遍历可能的分割点。对于每个分割点，我们将其转换为数字curNum。注意要处理以0开头的数字，除非分割点本身就是0，否则不允许出现以0开头的数字。
5. 将curNum与前两个数字num1和num2进行比较，如果count大于等于2且curNum不等于num1 + num2，则继续下一个循环，尝试下一个分割点。
6. 如果curNum与num1 + num2相等，那么递归调用backtrack函数，传入更新后的索引i + 1，更新后的前两个数字num2和curNum，以及count + 1。
7. 如果递归调用返回true，则说明已经找到累加数，直接返回true。
8. 如果循环结束后没有找到累加数，返回false。

下面是完整的题解实现：

import java.util.*;

public class Solution {
    /**
     * 判断给定的字符串是否是累加数
     *
     * @param num 字符串数字
     * @return 若是累加数返回true，否则返回false
     */
    public boolean AdditiveArray(String arr) {
        if (arr.length() < 3) {
            return false;
        }
        return backtrack(arr, 0, 0, 0, 0);
    }

    /**
     * 回溯法判断累加数
     *
     * @param num   字符串数字
     * @param index 当前索引
     * @param num1  前一个数字
     * @param num2  前两个数字
     * @param count 当前已找到的数字个数
     * @return 若是累加数返回true，否则返回false
     */
    private boolean backtrack(String arr, int index, long num1, long num2,
                              int count) {
        // 如果已经遍历完整个字符串，检查已找到的数字个数是否大于等于3
        if (index == arr.length()) {
            return count >= 3;
        }

        // 循环遍历可能的分割点
        for (int i = index; i < arr.length(); i++) {
            // 处理以0开头的数字，除非分割点本身就是0，否则不允许以0开头
            if (arr.charAt(index) == '0' && i > index) {
                break;
            }

            // 将分割点转换为数字
            long curNum = Long.parseLong(arr.substring(index, i + 1));
            if (curNum > Integer.MAX_VALUE) {
                break;
            }

            // 如果已找到的数字个数大于等于2且当前数字不等于前两个数字之和，则继续下一个循环
            if (count >= 2 && curNum != num1 + num2) {
                continue;
            }

            // 递归调用，传入更新后的索引、前两个数字和已找到的数字个数
            if (backtrack(arr, i + 1, num2, curNum, count + 1)) {
                return true;
            }
        }

        return false;
    }
}

该算法使用了回溯法来判断输入字符串是否为累加数。时间复杂度取决于字符串的长度，为O(N^2*2^(N/2))，其中N是输入字符串的长度。