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

这道题到底在问什么

输入

num="123456579"

输出

[123, 456, 579]　（123+456=579）

输入

num="0123"

输出

[]　（每段不能前导零,01 不合法）

先想最直接的笨办法

回溯。第二个数取 1 走不通,把它撤掉,退回只有第一个数 1 的状态,改让第二个数拉长一点试试。（动画第 9 步）

最优解：一步一步想明白

1. 3记牢这套「定种子 → 后续被和锁死 → 拼不出就回溯」,下面每一帧都在套它。
2. 4先把整串 1101111 摆出来,一共 7 位。我们要把它切成一段段数字,让它满足斐波那契规则。先从最左边、最短的种子开始试。
3. 5先定第一个种子。从下标 0 取最短的一位,第一个数 = 1。绿色标的就是当前正在用的这一段。
4. 6再定第二个种子,取下标 1 的 1,第二个数 = 1。两个种子定下来是 [1, 1],蓝色是已经定死的段。接下来每个数都被它俩锁死了。
5. 7第三个数的目标 = 前两数之和 = 1 加 1 = 2。从下标 2 往后拼,先看下标 2 是 0。
6. 8下标 2 单独是 0,0 不等于 2;想再往右拼成 01 又犯了前导零,不允许。这个位置怎么都凑不出 2,失败。
7. 9回溯。第二个数取 1 走不通,把它撤掉,退回只有第一个数 1 的状态,改让第二个数拉长一点试试。
8. 10第二个数改成取下标 1 到 2 的 10,第二个数 = 10。两个种子变成 [1, 10],重新往后推。
9. 11第三个数目标 = 1 加 10 = 11。从下标 3 往后拼,先看下标 3 是 1。
10. 12单独一个 1 才 1,比目标 11 小,不够。那就把这一段往右多拼一位,看下标 3 到 4。
11. 13下标 3 到 4 拼出 11,正好等于目标 11,命中!收进序列,现在是 [1, 10, 11]。继续往后推下一个数。
12. 14下一个目标 = 10 加 11 = 21。可剩下只有下标 5、6 这两位,最多拼成 11,离 21 差得远。
13. 15一直拼到字符串末尾,最大也只有 11,凑不出 21,这条路又断了。第一个数取 1 时,第二个数取 1、取 10 这两条分支都走死了;其余更长的第二个种子(101、1011…),要么拼出的数超过目标仍不命中,要么剩余位数不足,同样失败,这里折叠展示。所以第一个数取 1 的各种走法确实试遍了,仍不行。
14. 16大回溯。第一个数定成 1 的所有分支都走死了,把它也撤掉,改用更长的第一个数重新开局。
15. 17第一个数改成取下标 0 到 1 的 11,第一个数 = 11。重新来定第二个种子。
16. 18第二个数取下标 2 的 0。注意单独一个 0 是允许的,只有像 01 那样 0 打头才算前导零。两个种子定为 [11, 0]。
17. 19第三个数目标 = 11 加 0 = 11。从下标 3 往后拼,先看下标 3 是 1。
18. 20单独的 1 比 11 小,不够,把这段往右拼一位,看下标 3 到 4。
19. 21下标 3 到 4 拼出 11,等于目标 11,命中!序列变成 [11, 0, 11]。继续往后推。
20. 22再下一个目标 = 0 加 11 = 11。从下标 5 往后拼,下标 5 是 1,偏小。
21. 23把这段拼到下标 5 到 6,得到 11,又一次正好命中目标 11!序列变成 [11, 0, 11, 11]。
22. 24下标正好用到字符串末尾,序列有 4 个数,满足至少 3 个、且每个都是前两数之和。拆分成功,答案 [11, 0, 11, 11]。
23. 25回放一遍:11 加 0 等于第三个 11,0 加第三个 11 等于第四个 11,每一步都对得上,这就是一条合法的斐波那契式拆分。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        def dfs(i):
            if i == n:
                return len(ans) > 2
            x = 0
            for j in range(i, n):
                if j > i and num[i] == '0':
                    break
                x = x * 10 + int(num[j])
                if x > 2**31 - 1 or (len(ans) >= 2 and x > ans[-2] + ans[-1]):
                    break
                if len(ans) < 2 or ans[-2] + ans[-1] == x:
                    ans.append(x)
                    if dfs(j + 1):
                        return True
                    ans.pop()
            return False

        n = len(num)
        ans = []
        dfs(0)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> splitIntoFibonacci(string num) {
        int n = num.size();
        vector<int> ans;
        function<bool(int)> dfs = [&](int i) -> bool {
            if (i == n) {
                return ans.size() > 2;
            }
            long long x = 0;
            for (int j = i; j < n; ++j) {
                if (j > i && num[i] == '0') {
                    break;
                }
                x = x * 10 + num[j] - '0';
                if (x > INT_MAX || (ans.size() > 1 && x > (long long) ans[ans.size() - 1] + ans[ans.size() - 2])) {
                    break;
                }
                if (ans.size() < 2 || x == (long long) ans[ans.size() - 1] + ans[ans.size() - 2]) {
                    ans.push_back(x);
                    if (dfs(j + 1)) {
                        return true;
                    }
                    ans.pop_back();
                }
            }
            return false;
        };
        dfs(0);
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private List<Integer> ans = new ArrayList<>();
    private String num;

    public List<Integer> splitIntoFibonacci(String num) {
        this.num = num;
        dfs(0);
        return ans;
    }

    private boolean dfs(int i) {
        if (i == num.length()) {
            return ans.size() >= 3;
        }
        long x = 0;
        for (int j = i; j < num.length(); ++j) {
            if (j > i && num.charAt(i) == '0') {
                break;
            }
            x = x * 10 + num.charAt(j) - '0';
            if (x > Integer.MAX_VALUE
                || (ans.size() >= 2 && x > ans.get(ans.size() - 1) + ans.get(ans.size() - 2))) {
                break;
            }
            if (ans.size() < 2 || x == ans.get(ans.size() - 1) + ans.get(ans.size() - 2)) {
                ans.add((int) x);
                if (dfs(j + 1)) {
                    return true;
                }
                ans.remove(ans.size() - 1);
            }
        }
        return false;
    }
}

复杂度

面试官可能追问