将数组拆分成斐波那契序列

LeetCode每日一题，842. Split Array into Fibonacci Sequence

先看题目描述

大意就是给定一个只含数字的字符串，问能够将该数字拆分成斐波那契序列，斐波那契序列的定义是数组 F 满足每个元素都在 32 位有符号非负整数的范围内，F 的长度大于等于 3，且 F[i + 2] = F[i + 1] + F[i] 。拆分时还有一点需要注意，拆分的数字中不能有多余的 0，即拆分的数字第一位不能为 0，除非它是 0 本身

算法和思路

这题一开始一直在往贪心算法方面想，想不出来就去看题解，才发现用回溯和剪枝就行

回溯+剪枝

将给定的字符串拆分成斐波那契式序列，可以通过回溯的方法实现

使用列表存储拆分出的数，回溯过程中维护该列表的元素，列表初始为空。遍历字符串的所有可能的前缀，作为当前被拆分出的数，然后对剩余部分继续拆分，直到整个字符串拆分完毕

根据斐波那契式序列的要求，从第 3 个数开始，每个数都等于前 2 个数的和，因此从第 3 个数开始，需要判断拆分出的数是否等于前 2 个数的和，只有满足要求时才进行拆分，否则不进行拆分

回溯过程中，还有三处可以进行剪枝操作

拆分出的数如果不是 0，则不能以 0 开头，因此如果字符串剩下的数以 0 开头，就不需要考虑拆分出长度大于 1 的数，因为长度大于 1 的数以 0 开头是不符合要求的
若拆分出的数超出了 32 位有符号整数类型表示的范围，则进行剪枝，因为题目中要求了返回的斐波那契序列中每个数都要在 32 位有符号非负整数的范围内
若列表中已经有至少 2 个数了，且拆分出的数大于其前 2 个数之和，那么就没必要继续尝试了，不可能继续拆分得到斐波那契序列，直接剪枝即可

当整个字符串拆分完毕时，如果列表中至少有 3 个数，则得到一个符合要求的斐波那契式序列，返回列表。如果没有找到符合要求的斐波那契式序列，则返回空列表

实现方面，回溯需要带返回值，表示是否存在符合要求的斐波那契式序列

算法源码

下面是自己看了题解后用回溯 + 剪枝实现的源码

import java.util.*;

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        int len = S.length();
        List<Integer> res = new ArrayList<>();
        int[] s = new int[len];
        for (int i = 0; i < len; i++) {
            s[i] = S.charAt(i) - '0';
        }
        backTrack(res, s, len, 0, 0, 0);
        return res;
    }

    private boolean backTrack(List<Integer> res, int[] s, int len, int index, int sum, int prev) {
        if (index == len) {
            return res.size() >= 3;
        }
        long curLong = 0;
        for (int i = index; i < len; i++) {
            if (i > index && s[index] == 0) {
                break;
            }
            curLong = curLong * 10 + s[i];
            if (curLong > Integer.MAX_VALUE) {
                break;
            }
            int cur = (int)curLong;
            if (res.size() >= 2) {
                if (cur > sum) {
                    break;
                } else if (cur < sum) {
                    continue;
                }
            }
            res.add(cur);
            if (backTrack(res, s, len, i + 1, cur + prev, cur)) {
                return true;
            } else {
                res.remove(res.size() - 1);
            }
        }
        return false;
    }
}