LeetCode 842. Split Array into Fibonacci Sequence

原题链接在这里：https://leetcode.com/problems/split-array-into-fibonacci-sequence/

题目：

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

• 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
• F.length >= 3;
• and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

1. 1 <= S.length <= 200
2. S contains only digits.

题解：

The quesiton is asking for any sequence, not all of them.

Thus DFS state needs s, current starting index, current list item. DFS returns if s could be cut into Fibonacci sequence.

If any DFS comes to true, then just return current list, there is no need to do further more calculation.

For i >= start index, get the candidate from starting index, if it exceeds Integer, return false.

If current list item already has >= 2 items, but candidate != last 2 values sum, return false.

If current list item has 0 or 1 item, or has >= 2 items, but candidate == last 2 values sum, add candidate to res and continue DFS. 

When gettting candidate, starting index could point to ‘0‘, ‘0‘ as candidate is fine, but ‘01‘ is not. 

Thus here it needs to check when i > start && s.charAt(start) == ‘0‘, return false.

Time Complexity: O(expontenial).

Space: O(n). n = s.length(). stack space.

AC Java:  

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> res = new ArrayList<>();
        if(S == null || S.length() == 0){
            return res;
        }
        
        dfs(S, 0, res);
        return res;
    }
    
    private boolean dfs(String s, int start, List<Integer> res){
        if(start == s.length() && res.size() > 2){
            return true;
        }
        
        for(int i = start; i<s.length(); i++){
            if(s.charAt(start) == ‘0‘ && i > start){
                return false;
            }
            
            long candidate = Long.valueOf(s.substring(start, i+1));
            if(candidate > Integer.MAX_VALUE){
                return false;
            }
            
            int size = res.size();
            if(size >= 2 && candidate > res.get(size-1)+res.get(size-2)){
                return false;
            }
            
            if(size < 2 || candidate == res.get(size-1)+res.get(size-2)){
                res.add((int)candidate);
                if(dfs(s, i+1, res)){
                    return true;
                }
                
                res.remove(res.size()-1);   
            }
        }
        
        return false;
    }
}