給定一個數字字符串 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 {public List<Integer> splitIntoFibonacci(String S) {split(S,0,new ArrayList<>());return total==null?new ArrayList<>():total;}ArrayList<Integer> total;boolean flag=false;public void split(String S,int pos,List<Integer> list) {if(flag) return;//已經找到了if(list.size()>2&&pos==S.length())//遍歷完了{flag=true;total=new ArrayList<>(list);return;}for(int len=1;len+pos<=S.length()&&len<11;len++){String sub=S.substring(pos,pos+len);if(len>1&&sub.charAt(0)=='0') break;//第一位是0long temp=Long.parseLong(sub);if(temp>Integer.MAX_VALUE) break;//已經溢出了if(list.size()<2||list.get(list.size()-1)+list.get(list.size()-2)==temp)//滿足條件{list.add((int)temp);split(S,pos+len,list);list.remove(list.size()-1);//回溯}}}
}