題目

給定一個數字字串 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]

示例 2：輸入: "11235813" 輸出: [1,1,2,3,5,8,13]

示例 3：輸入: "112358130" 輸出: []

解釋: 這項任務無法完成。

示例 4：輸入："0123" 輸出：[]

解釋：每個塊的數字不能以零開頭，因此 "01"，"2"，"3" 不是有效答案。

示例 5：輸入: "1101111" 輸出: [110, 1, 111]

解釋: 輸出 [11,0,11,11] 也同樣被接受。

提示：1 <= S.length <= 200

字串 S 中只含有數字。

解題思路分析

1、回溯；時間複雜度O(n(log(n))^2)，空間複雜度O(n)

var res []intfunc splitIntoFibonacci(S string) []int {	res = make([]int, 0)	dfs(S, 0, 0, 0, make([]int, 0))	return res}func dfs(s string, index, sum, prev int, path []int) bool {	if index == len(s) {		if len(path) >= 3 {			res = path		}		return len(path) >= 3	}	value := 0	for i := index; i < len(s); i++ {		// 0開頭不滿足要求(當前i=index的時候，可以為0， 避免錯過1+0=1的情況)		if s[index] == '0' && i > index {			break		}		value = value*10 + int(s[i]-'0')		if value > math.MaxInt32 {			break		}		if len(path) >= 2 {			if value < sum {				continue			}			if value > sum {				break			}		}		if dfs(s, i+1, prev+value, value, append(path, value)) == true {			return true		}	}	return false}

總結

Medium題目，使用回溯嘗試不同的組合