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
| class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
ans = []
self.helper(S, ans, 0)
return ans
def helper(self, s, ans, idx):
if idx == len(s) and len(ans) >= 3:
return True
for i in range(idx, len(s)):
if s[idx] == '0' and i > idx:
break
num = int(s[idx: i + 1])
if num > 2**31 - 1:
break
size = len(ans)
# early termination
if size >= 2 and num > ans[size - 1] + ans[size - 2]:
break
if size <= 1 or num == ans[size - 1] + ans[size - 2]:
ans.append(num)
# branch pruning. if one branch has found fib seq, return true to upper call
if self.helper(s, ans, i + 1):
return True
ans.pop()
return False
|