LeetCode-842

题目

结果

代码

这题没思路，参考题解做的，不得不说，题解的代码写的非常漂亮，建议全文背诵，经典永流传。

返回值用boolean的递归我真的得第一次见，那个remove是点睛之笔。

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> ans = new ArrayList<>();
        recursive(ans, S, 0, 0, 0);
        return ans;
    }

    private boolean recursive(List<Integer> ans, String nums, int index, int sum, int prev) {
        // 递归终止条件
        if (index == nums.length()) {
            return ans.size() >= 3;
        }

        long curr = 0;
        for (int i = index; i < nums.length(); i++) {
            // 以0开始，剪枝
            if (i > index && nums.charAt(index) == '0') {
                return false;
            }

            curr = curr * 10 + Integer.parseInt(String.valueOf(nums.charAt(i)));
            // 越界，剪枝
            if (curr > Integer.MAX_VALUE) {
                return false;
            }

            if (ans.size() >= 2) {
                // 需要更多位
                if (curr < sum) {
                    continue;
                } else if (curr > sum) {
                    // 剪枝
                    return false;
                }
            }
            ans.add((int) curr);
            if (recursive(ans, nums, i + 1, (int) curr + prev, (int) curr)) {
                return true;
            } else {
                // 真*剪枝
                ans.remove(ans.size() - 1);
            }
        }
        return false;
    }
}

复杂度

时间复杂度：不会算

空间复杂度：O（N），递归最多N层