LeetCode 842. Split Array into Fibonacci Sequence

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> ans = new ArrayList<>();
        backtrack(S, 0, 0,  0, ans);
        return ans;
    }

    private boolean backtrack(String S, int index, int sum, int prev, List<Integer> ans) {
        if (index == S.length())
            return ans.size() >= 3;
        long currLong = 0;
        for (int i = index; i < S.length(); i++) {
            if (i > index && S.charAt(index) == '0') break;
            currLong = currLong * 10 + S.charAt(i) - '0';
            if (currLong > Integer.MAX_VALUE) break;
            int curr = (int) currLong;
            if (ans.size() >= 2) {
                if (curr < sum) continue;
                if (curr > sum) break;
            }
            ans.add(curr);
            if (backtrack(S, i + 1, prev + curr, curr, ans))
                return true;
            ans.remove(ans.size() - 1);
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        vector<int> ans;
        const int len = S.size();
        function<bool(int, int, int)> backtrack = [&](int index, int sum, int prev) {
            if (index == len) {
                return ans.size() >= 3;
            }
            long long curr = 0;
            for (int i = index; i < len; ++i) {
                if (i > index && S[index] == '0') break;
                curr = curr * 10 + S[i] - '0';
                if (curr > INT_MAX) break;
                if (ans.size() >= 2) {
                    if (curr < sum) continue;
                    if (curr > sum) break;
                }
                ans.push_back(curr);
                if (backtrack(i + 1, prev + curr, curr))
                    return true;
                ans.pop_back();
            }
            return false;
        };
        backtrack(0, 0, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = list()
        def backtrack(index: int):
            if index == len(S):
                return len(ans) >= 3
            curr = 0
            for i in range(index, len(S)):
                if i > index and S[index] == "0": break
                curr = curr * 10 + ord(S[i]) - ord("0")
                if curr > 2**31 - 1: break
                if len(ans) >= 2:
                    if curr < ans[-2] + ans[-1]: continue
                    if curr > ans[-2] + ans[-1]: break
                ans.append(curr)
                if backtrack(i + 1):
                    return True
                ans.pop()
            return False

        backtrack(0)
        return ans