給定一個數字字符串 S，比如 S = “123456579”，我們可以將它分成斐波那契式的序列 [123, 456, 579]。

形式上，斐波那契式序列是一個非負整數列表 F，且滿足：

0 <= F[i] <= 2^31 - 1，（也就是說，每個整數都符合 32 位有符號整數類型）；
F.length >= 3；
對于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
另外，請注意，將字符串拆分成小塊時，每個塊的數字一定不要以零開頭，除非這個塊是數字 0 本身。

返回從 S 拆分出來的任意一組斐波那契式的序列塊，如果不能拆分則返回 []。

示例 1：

輸入：“123456579”
輸出：[123,456,579]

解題思路

窮舉前兩個數字，前兩個數字確定了，斐波那契數列也就確定了，只需要檢查后面的字符串是不是滿足斐波那契數列即可。

代碼

class Solution {List<Integer> tarr=new ArrayList<>();public List<Integer> splitIntoFibonacci(String S) {for(int i=1;i<= Math.ceil((double)S.length()/3);i++)//窮舉第一個數字{int sec=i;if(S.charAt(0)=='0'&&i>1) break;//0開頭的排除long c=Long.parseLong(S.substring(0,i));if(c>Integer.MAX_VALUE) break;//大于int最大值的排除tarr.add(Integer.parseInt(S.substring(0,i)));for(int j=sec+1;j<=Math.ceil((double)(S.length()*2)/3);j++)//窮舉第二個數字{if(S.charAt(sec)=='0'&&j>sec+1) break;long temp=Long.parseLong(S.substring(sec,j));if(temp>Integer.MAX_VALUE) break;tarr.add(Integer.parseInt(S.substring(sec,j)));if(getFibonacci(S,j)) return tarr;//檢查后面的字符串tarr.remove(tarr.size()-1);//回溯}tarr.remove(tarr.size()-1);}tarr.clear();return tarr;}public boolean getFibonacci(String S,int s) {String tar=String.valueOf(tarr.get(tarr.size()-1)+tarr.get(tarr.size()-2));//要尋找的目標元素if(s==S.length()&&tarr.size()>2) return true;else if(s+tar.length()>S.length()) return false;//遞歸邊界if(S.substring(s,s+tar.length()).equals(tar)) {tarr.add(Integer.parseInt(tar));if(!getFibonacci(S,s+tar.length())) {tarr.remove(tarr.size()-1);//回溯return false;}else return true;}else return false;}
}