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 <= S.length <= 200
S contains only digits.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Complete search

Starter code: class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        

Solutions:
class Solution:

	def splitIntoFibonacci(self, S):
		for i in range(min(10, len(S))):
			x = S[:i + 1]
			if x != '0' and x.startswith('0'):
				break
			a = int(x)
			for j in range(i + 1, min(i + 10, len(S))):
				y = S[i + 1:j + 1]
				if y != '0' and y.startswith('0'):
					break
				b = int(y)
				fib = [a, b]
				k = j + 1
				while k < len(S):
					nxt = fib[-1] + fib[-2]
					nxtS = str(nxt)
					if nxt <= 2 ** 31 - 1 and S[k:].startswith(nxtS):
						k += len(nxtS)
						fib.append(nxt)
					else:
						break
				else:
					if len(fib) >= 3:
						return fib
		return []


class Solution:

	def splitIntoFibonacci(self, S: str):
		self.res = []
		self.dfs(S, [], 0)
		return self.res

	def dfs(self, S, temp, count):
		if not S and count >= 3:
			self.res = temp[:]
			return
		for step in range(1, min(len(S) + 1, 11)):
			val = S[:step]
			if str(int(val)) == val and 0 <= int(val) <= pow(2, 31) - 1:
				if count < 2:
					temp.append(int(val))
					self.dfs(S[step:], temp, count + 1)
					temp.pop()
				elif temp[count - 2] + temp[count - 1] == int(val):
					temp.append(int(val))
					self.dfs(S[step:], temp, count + 1)
					temp.pop()


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def backtrack(path=[], i=0):
			if i == len(S):
				return path if len(path) >= 3 else []
			for j in range(i + 1, min(i + 10, len(S)) + 1):
				if S[i] == '0' and j > i + 1:
					continue
				x = int(S[i:j])
				if x < 2 ** 31 and (len(path) < 2 or (len(path) >= 2 and x == sum(path[-2:]))):
					new = backtrack(path + [x], j)
					if new:
						return new
			return []
		return backtrack()


class Solution:

	def dfs(self, final, S, path, original):
		if not S and len(path) > 2 and all([int(i) <= 2 ** 31 - 1 for i in path]):
			final.append(path)
		for i in range(1, len(S) + 1):
			temp = int(S[:i])
			if i > 1 and S[:i][0] == '0':
				continue
			if int(S[:i]) >= 2 ** 31 - 1:
				return
			if len(path) < 2 or (len(path) >= 2 and int(path[-1]) + int(path[-2]) == temp):
				self.dfs(final, S[i:], path + [S[:i]], original)

	def splitIntoFibonacci(self, S: str) -> List[int]:
		final = []
		path = []
		self.dfs(final, S, path, S)
		if final:
			return final[0]
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		BIG_NUMBER = 2 ** 31 - 1
		numSplits = {}
		sLength = len(S)
		reverseSplits = {}
		for i in range(sLength):
			currentNum = 0
			for j in range(i + 1, sLength + 1):
				currentNum *= 10
				currentNum += int(S[j - 1])
				if currentNum == 0:
					numSplits[i, j] = currentNum
					if currentNum not in reverseSplits:
						reverseSplits[currentNum] = {}
					if i not in reverseSplits[currentNum]:
						reverseSplits[currentNum][i] = set([j])
					else:
						reverseSplits[currentNum][i].add(j)
					break
				elif currentNum > BIG_NUMBER:
					break
				else:
					numSplits[i, j] = currentNum
					if currentNum not in reverseSplits:
						reverseSplits[currentNum] = {}
					if i not in reverseSplits[currentNum]:
						reverseSplits[currentNum][i] = set([j])
					else:
						reverseSplits[currentNum][i].add(j)
		fibonacciSequences = {}

		def computeFibonacciSequences(startingIndex):
			if startingIndex not in fibonacciSequences:
				if startingIndex == sLength:
					answer = [[]]
				else:
					answer = []
					for i in range(startingIndex + 1, sLength + 1):
						if (startingIndex, i) in numSplits:
							nextNumber = numSplits[startingIndex, i]
							ithFibonaccis = computeFibonacciSequences(i)
							for fibSeq in ithFibonaccis:
								if len(fibSeq) > 1:
									largeNumber = fibSeq[-2]
									smallNumber = fibSeq[-1]
									if nextNumber == largeNumber - smallNumber:
										appended = fibSeq + [nextNumber]
										answer.append(appended)
								else:
									appended = fibSeq + [nextNumber]
									answer.append(appended)
						else:
							break
				fibonacciSequences[startingIndex] = answer
				return answer
			else:
				return fibonacciSequences[startingIndex]
		computeFibonacciSequences(0)
		for sequence in fibonacciSequences[0]:
			if len(sequence) >= 3:
				sequence.reverse()
				return sequence
		else:
			return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def f(l, i):
			if i == len(S) and len(l) >= 3:
				return l
			r = []
			t = 0
			for j in range(i, len(S)):
				t *= 10
				t += int(S[j])
				if t <= 2 ** 31 - 1:
					if len(l) > 1 and l[-1] + l[-2] != t:
						continue
					l.append(t)
					temp = f(l, j + 1)
					if temp:
						return temp
					l.pop()
					if t == 0:
						return []
			return r
		return f([], 0)


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		n = len(S)
		for i in range(1, min(32, (n - 1) // 2 + 1)):
			for j in range(i + 1, 2 * n // 3 + 1):
				(a, b) = (int(S[:i]), int(S[i:j]))
				idx = len(str(a + b))
				tmp = [a, b]
				l = j
				while int(S[l:l + idx]) == a + b:
					if int(S[l:l + idx]) > 2 ** 31 - 1:
						break
					tmp.append(int(S[l:l + idx]))
					if l + idx == n:
						return tmp
					a = b
					b = int(S[l:l + idx])
					l += idx
					idx = len(str(a + b))
		return []


class Solution:

	def trysolve(self, s, seq, n):
		seq.append(n)
		if self.solve(s, seq):
			return True
		seq.pop()
		return False

	def solve(self, s, seq):
		if not s:
			return True
		target = sum(seq[-2:])
		if target > 2 ** 31 - 1:
			return False
		if s[0] == '0':
			if target == 0:
				return self.trysolve(s[1:], seq, 0)
			else:
				return False
		for end in range(1, len(s) + 1):
			n = int(s[:end])
			if n == target and self.trysolve(s[end:], seq, n):
				return True
		return False

	def splitIntoFibonacci(self, S: str) -> List[int]:
		limit = 2 ** 31 - 1
		for i in range(1, len(S)):
			n1 = int(S[:i])
			if n1 > limit:
				return []
			if n1 != 0 and S[0] == '0':
				return []
			for j in range(i + 1, len(S)):
				n2 = int(S[i:j])
				if n2 != 0 and S[i] == '0':
					break
				if n2 > limit:
					break
				seq = [n1, n2]
				if self.solve(S[j:], seq):
					return seq
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		(n, ans) = (len(S), [])

		def dfs(pos):
			if pos == n:
				return len(ans) >= 3
			num = 0
			for i in range(pos, n):
				if S[pos] == '0' and i == pos or S[pos] != '0':
					num = num * 10 + ord(S[i]) - ord('0')
					if num < 2 ** 31 - 1:
						if len(ans) < 2 or ans[-1] + ans[-2] == num:
							ans.append(num)
							if dfs(i + 1):
								return True
							ans.pop()
			return False
		dfs(0)
		return ans


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def startswith(S, k, x):
			y = 0
			for i in range(k, len(S)):
				y = 10 * y + int(S[i])
				if y == x:
					return i - k + 1
				elif y > x:
					break
			return 0
		MAX_INT = 2 ** 31 - 1
		a = 0
		for i in range(len(S) - 2):
			a = 10 * a + int(S[i])
			b = 0
			for j in range(i + 1, len(S) - 1):
				b = 10 * b + int(S[j])
				fib = [a, b]
				k = j + 1
				while k < len(S):
					if fib[-2] > MAX_INT - fib[-1]:
						break
					c = fib[-2] + fib[-1]
					length = startswith(S, k, c)
					if length == 0:
						break
					fib.append(c)
					k += length
				else:
					return fib
				if b == 0:
					break
			if a == 0:
				break
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		exp = 2 ** 31 - 1

		def works(x, y, i):
			res = [x, y]
			while i < len(S):
				target = res[-2] + res[-1]
				if target > exp:
					return []
				build = S[i]
				i += 1
				while i < len(S) and build < target:
					if build == 0:
						return []
					build = build * 10 + S[i]
					i += 1
				if build != target:
					return []
				res.append(build)
			return res
		S = [int(c) for c in S]
		N = len(S)
		x = 0
		for i in range(N - 2):
			if i > 0 and x == 0:
				break
			x = x * 10 + S[i]
			y = 0
			for j in range(i + 1, N - 1):
				if j > i + 1 and y == 0:
					break
				y = y * 10 + S[j]
				res = works(x, y, j + 1)
				if res:
					return res
		return []


class Solution:

	def dfs(self, grandpa, parent, S, start):
		if start >= len(S):
			return ([], True)
		for i in range(start + 1, len(S) + 1):
			sub = S[start:i]
			if len(sub) > 1 and sub[0] == '0':
				continue
			num = int(sub)
			if num > 2 ** 31 - 1:
				continue
			if grandpa >= 0 and parent >= 0 and (num != grandpa + parent):
				continue
			(ans, found) = self.dfs(parent, num, S, i)
			if grandpa < 0 and parent < 0 and (len(ans) < 2):
				continue
			if found:
				return ([num] + ans, True)
		return ([], False)

	def splitIntoFibonacci(self, S: str) -> List[int]:
		return self.dfs(-1, -1, S, 0)[0]


class Solution:

	def splitIntoFibonacci(self, S):
		self.res = []

		def dfs(index, prev2, prev, count, cur_path):
			if index == len(S) and count >= 3:
				self.res = cur_path
				return
			for i in range(index, len(S)):
				x = int(S[index:i + 1])
				if count == 0:
					dfs(i + 1, 0, x, count + 1, cur_path + [x])
				else:
					if x > 1 << 31:
						return False
					if x == prev2 + prev or count == 1:
						if dfs(i + 1, prev, x, count + 1, cur_path + [x]):
							return True
				if x == 0:
					break
		dfs(0, 0, 0, 0, [])
		return self.res


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def check(i, a, b):
			if int(a) > 2147483647 or int(b) > 2147483647:
				return ([], False)
			if i == len(S):
				return ([str(a), str(b)], True)
			s = str(a + b)
			if S[i:i + len(s)] == s:
				(out, good) = check(i + len(s), b, int(s))
				if good:
					return ([str(a)] + out, True)
			return ([], False)
		for i in range(len(S) - 2):
			a = int(S[:i + 1])
			if S[0] == '0' and a != 0:
				break
			for j in range(i + 1, len(S) - 1):
				b = int(S[i + 1:j + 1])
				if S[i + 1] == '0' and b != 0:
					break
				(out, _) = check(j + 1, a, b)
				if out:
					return out
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def helper(a, i, j, cur_ans):
			if S[i] == '0' and j != i + 1:
				cur_ans = []
				return False
			if a > 2 ** 31 - 1:
				return False
			b = int(S[i:j])
			c = a + b
			if b > 2 ** 31 - 1 or c > 2 ** 31 - 1:
				return False
			c_s = str(c)
			if c_s == S[j:j + len(c_s)]:
				k = j + len(c_s)
				cur_ans.append(c)
				if k == len(S):
					return True
				if helper(b, j, k, cur_ans):
					return True
				else:
					cur_ans = []
					return False
			cur_ans = []
			return False
		if len(S) == 0:
			return []
		for i in range(1, len(S)):
			if i > 1 and S[0] == '0':
				break
			a = int(S[:i])
			for j in range(i + 1, len(S)):
				cur_ans = [a, int(S[i:j])]
				if helper(a, i, j, cur_ans):
					return cur_ans
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		for i in range(len(S))[::-1]:
			for j in range(i + 1, len(S)):
				(b, c) = (int(S[i:j]), int(S[j:]))
				if c >= 2 ** 31:
					continue
				if b >= 2 ** 31:
					continue
				parts = [b, c]
				a = c - b
				while a >= 0 and a <= 2 ** 31 - 1:
					parts.insert(0, a)
					(b, c) = (a, b)
					a = c - b
					if S == ''.join(map(str, parts)):
						return parts
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		ans = []
		limit = 2 ** 31 - 1

		def helper(n, prefix):
			nonlocal S, ans
			if ans:
				return
			if n == len(S):
				ans = prefix
				return
			num = sum(prefix[-2:])
			if S[n:].startswith(str(num)) and num <= limit:
				return helper(n + len(str(num)), prefix + [num])
		for i in range(2, len(S) * 2 // 3 + 1):
			for j in range(1, i):
				helper(i, [int(S[:j]), int(S[j:i])])
				if ans:
					break
			if ans:
				break
		return ans


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def impl(s, pos, output):
			if pos >= len(s):
				return len(output) >= 3
			loop_end = len(s) + 1
			if s[pos] == '0':
				loop_end = pos + 2
			for p in range(pos + 1, loop_end):
				this_number = int(s[pos:p])
				if this_number > pow(2, 31) - 1:
					continue
				if len(output) >= 2 and output[-1] + output[-2] == this_number:
					output.append(this_number)
					if impl(s, p, output):
						return True
					else:
						output.pop()
				elif len(output) < 2:
					output.append(this_number)
					if impl(s, p, output):
						return True
					else:
						output.pop()
			return False
		result = []
		impl(S, 0, result)
		return result


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		ans = []
		limit = 2 ** 31 - 1

		@lru_cache(None)
		def helper(n, prefix):
			nonlocal S, ans
			if n == len(S):
				ans = prefix
				return
			num = int(S[prefix[-2]:prefix[-1]]) + int(S[prefix[-1]:n])
			if S[n:].startswith(str(num)) and num <= limit:
				return helper(n + len(str(num)), prefix + (n,))
		for i in range(2, len(S) * 2 // 3 + 1):
			for j in range(1, i):
				helper(i, (0, j))
				if ans:
					break
			if ans:
				break
		return [int(S[i:j]) for (i, j) in zip(ans, ans[1:] + (len(S),))] if ans else []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def dfs(index, res, s):
			if index == len(s) and len(res) >= 3:
				return True
			num = 0
			for i in range(index, len(s)):
				num = num * 10 + (ord(s[i]) - ord('0'))
				if num > 2 ** 31 - 1:
					break
				if len(res) > 2 and num > res[-1] + res[-2]:
					break
				if s[index] == '0' and i > index:
					break
				if len(res) < 2 or res[-1] + res[-2] == num:
					res.append(num)
					if dfs(i + 1, res, s):
						return True
					res.pop()
			return False
		result = []
		dfs(0, result, S)
		return result


class Solution:

	def ok(self, S, j, res):
		if j == len(S):
			return True
		for k in range(j + 1, len(S) + 1):
			third = S[j:k]
			if len(third) > 1 and third[0] == '0' or int(third) >= 2 ** 31:
				continue
			third = int(third)
			if third == res[-1] + res[-2]:
				res.append(third)
				if self.ok(S, k, res):
					return True
				else:
					res.pop()
		return False

	def splitIntoFibonacci(self, S: str) -> List[int]:
		n = len(S)
		res = []
		for i in range(1, n - 1):
			first = S[0:i]
			if len(first) > 1 and first[0] == '0' or int(first) >= 2 ** 31:
				continue
			for j in range(i + 1, n):
				second = S[i:j]
				if len(second) > 1 and second[0] == '0' or int(second) >= 2 ** 31:
					continue
				res = [int(first), int(second)]
				if self.ok(S, j, res):
					return res
				else:
					res = []
		return res


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def helper(S: str, curr_path: List[int]):
			if not S:
				if self.isValidPath(curr_path):
					return curr_path
				return None
			for partition_point in range(1, len(S) + 1):
				(prefix, suffix) = (S[:partition_point], S[partition_point:])
				valid_prefix = prefix == '0' or (prefix[0] != '0' and int(prefix) <= 2 ** 31 - 1)
				new_curr_path = curr_path + [int(prefix)]
				if valid_prefix and (len(new_curr_path) < 3 or self.isValidPath(new_curr_path)):
					recurse = helper(suffix, new_curr_path)
					if recurse:
						return recurse
			return None
		return helper(S, [])

	def isValidPath(self, path: List[str]) -> bool:
		return len(path) > 2 and int(path[-1]) == int(path[-2]) + int(path[-3])


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		if len(S) < 3:
			return []
		for i in range(1, len(S) - 2):
			first = S[:i]
			for j in range(i, len(S) - 1):
				j += 1
				second = S[i:j]
				split = self.dfs(first, second, S[j:], [first, second])
				if split:
					return split
		return []

	def notvalid(self, s):
		if int(s) != 0 and s[0] == 0:
			return True
		if int(s) > 2 ** 31 - 1:
			return True
		return False

	def dfs(self, s1, s2, rem, seq):
		if self.notvalid(s1) or self.notvalid(s2):
			return []
		s3 = str(int(s1) + int(s2))
		if self.notvalid(s3):
			return []
		l = len(s3)
		if rem[:l] == s3:
			seq.append(s3)
			if len(rem) > l:
				return self.dfs(s2, s3, rem[l:], seq)
			else:
				return seq
		return []


class Solution:

	def __init__(self):
		self.q = []

	def splitIntoFibonacci(self, s: str) -> List[int]:
		self.dfs(s, [], 0)
		return self.q

	def dfs(self, s, q, i):
		if i == len(s):
			if len(q) >= 3:
				self.q = q[:]
			return len(q) >= 3
		for j in range(i, min(len(s), i + 10)):
			v = int(s[i:j + 1])
			b1 = v < 2 ** 31 - 1
			b2 = v == 0 or (v and s[i] != '0')
			b3 = len(q) < 2 or q[-1] + q[-2] == v
			if b1 and b2 and b3 and self.dfs(s, q + [v], j + 1):
				return True
		return False


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		for i in range(1, len(S) - 1):
			for j in range(i + 1, len(S)):
				first = to_number(S[:i])
				second = to_number(S[i:j])
				ans = [first, second]
				if is_valid_fibonacci(S, j, first, second, ans):
					return ans
		return []

def to_number(s):
	num = int(s)
	if s.startswith('0') and num != 0:
		return None
	if num < 0 or num > 2 ** 31 - 1:
		return None
	return num

def is_valid_fibonacci(s, curr_index, first, second, ans):
	if first is None or second is None:
		return False
	if curr_index == len(s):
		return True
	expected = first + second
	len_next_num = len(str(expected))
	end_index = curr_index + len_next_num
	next_num = to_number(s[curr_index:end_index])
	if next_num != expected:
		return False
	ans.append(next_num)
	return is_valid_fibonacci(s, end_index, second, next_num, ans)


class Solution:

	def get_values(self, s, idx):
		for i in range(idx, len(s)):
			yield (i, s[idx:i + 1])

	def splitIntoFibonacci(self, S: str) -> List[int]:
		for (i, a) in self.get_values(S, 0):
			if a != '0' and a.startswith('0'):
				break
			for (j, b) in self.get_values(S, i + 1):
				if b != '0' and b.startswith('0'):
					break
				k = j + 1
				out = [a, b]
				while k < len(S):
					v = int(a) + int(b)
					str_v = str(v)
					if v <= 2 ** 31 - 1 and S[k:].startswith(str_v):
						k = k + len(str_v)
						(a, b) = (b, str_v)
						out.append(v)
					else:
						break
				if len(out) >= 3:
					if len(''.join(map(str, out))) == len(S):
						return out
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def dfs1(prev, cur, pos):
			if pos == len(S) - 1:
				return True
			nex = prev + cur
			prev = cur
			cur = nex
			if cur > 2 ** 31 - 1:
				return False
			if S[pos + 1:pos + 1 + len(str(nex))] == str(nex):
				if len(S[pos + 1:pos + 1 + len(str(nex))]) != 1 and S[pos + 1:pos + 1 + len(str(nex))][0] == '0':
					return False
				else:
					return dfs1(prev, cur, pos + len(str(nex)))
			else:
				return False

		def dfs2(res, prev, cur, pos):
			res.append(prev)
			if pos == len(S) - 1:
				res.append(cur)
				return
			nex = prev + cur
			prev = cur
			cur = nex
			dfs2(res, prev, cur, pos + len(str(nex)))
		for i in range(len(S) - 1):
			for j in range(i + 1, len(S) - 1):
				if len(S[:i + 1]) > 1 and S[:i + 1][0] == '0' or (len(S[i + 1:j + 1]) > 1 and S[i + 1:j + 1][0] == '0'):
					continue
				if dfs1(int(S[:i + 1]), int(S[i + 1:j + 1]), j):
					res = []
					dfs2(res, int(S[:i + 1]), int(S[i + 1:j + 1]), j)
					return res
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		stack = []

		def solve(index):
			if stack and int(stack[-1]) > 2 ** 31 - 1:
				return False
			if index == len(S):
				return len(stack) >= 3
			if len(stack) < 2:
				if S[index] == '0':
					stack.append('0')
					if solve(index + 1):
						return True
					stack.pop()
					return False
				for i in range(index, len(S)):
					stack.append(S[index:i + 1])
					if solve(i + 1):
						return True
					stack.pop()
			elif int(stack[-1]) + int(stack[-2]) > int(S[index:]):
				return False
			else:
				if S[index] == '0':
					if stack[-1] == '0' and stack[-2] == '0':
						stack.append('0')
						if solve(index + 1):
							return True
						stack.pop()
					return False
				for i in range(index, len(S)):
					if int(stack[-1]) + int(stack[-2]) == int(S[index:i + 1]):
						stack.append(S[index:i + 1])
						if solve(i + 1):
							return True
						stack.pop()
			return False
		solve(0)
		return stack


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		res = []
		self.dfs(res, S, 0, [])
		return res[0] if res else []

	def dfs(self, res, S, index, path):
		if index == len(S) and len(path) >= 3:
			res.append(path[:])
			return
		for i in range(index + 1, len(S) + 1):
			if i > index + 1 and S[index] == '0' or int(S[index:i]) > 2 ** 31 - 1:
				return
			temp_num = int(S[index:i])
			if len(path) >= 2 and temp_num == path[-1] + path[-2] or len(path) < 2:
				path.append(temp_num)
				self.dfs(res, S, i, path)
				path.pop()


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def isFib(i, a, b, count):
			if i == len(S):
				return [] if count >= 3 else None
			if a > (1 << 31) - 1 or b > (1 << 31) - 1 or a + b > 1 << 31:
				return None
			if S[i:i + 1] == ['0'] and a != 0:
				return False
			j = i + len(str(a))
			if S[j:j + 1] == ['0'] and b != 0:
				return False
			if S[i:i + len(str(a + b))] != str(a + b):
				return False
			rest = isFib(i + len(str(a + b)), b, a + b, count + 1)
			if rest or rest == []:
				return [a + b] + rest
		for len_a in range(1, len(S)):
			for len_b in range(1, len(S)):
				str_a = S[:len_a]
				str_b = S[len_a:len_a + len_b]
				(a, b) = (int(str_a), int(str_b))
				if a > (1 << 31) - 1 or b > (1 << 31) - 1:
					continue
				if str_a[0] == '0' and len_a > 1 or (str_b[0] == '0' and len_b > 1):
					continue
				val = isFib(len_a + len_b, int(S[:len_a]), int(S[len_a:len_a + len_b]), 2)
				if val:
					return [int(str_a), int(str_b)] + val
				if S[0] == '0':
					break
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		N = len(S)
		for (i, j) in itertools.combinations(range(1, N), 2):
			(a, b) = (S[:i], S[i:j])
			if str(int(a)) != a or str(int(b)) != b or int(a) > 2 ** 31 - 1 or (int(b) > 2 ** 31 - 1):
				continue
			res = []
			res.append(a)
			while j < N:
				c = str(int(a) + int(b))
				if not S.startswith(c, j) or int(c) > 2 ** 31 - 1:
					res = []
					break
				res.append(b)
				(a, b) = (b, c)
				j += len(c)
			res.append(c)
			if j == N:
				return res
		return []


class Solution:

	def validFib(self, S, n1, n2, i, ret):
		if n1[0] != '0' and len(n1) >= 1 or n1 == '0':
			num1 = int(n1)
		else:
			return False
		if n2[0] != '0' and len(n2) >= 1 or n2 == '0':
			num2 = int(n2)
		else:
			return False
		num3 = num1 + num2
		n3 = str(num3)
		j = 0
		while j + i < len(S) and j < len(n3):
			c1 = n3[j]
			c2 = S[j + i]
			if c1 != c2:
				return False
			j += 1
		if len(n1) + len(n2) + len(n3) > len(S):
			return False
		if i + len(n3) == len(S) and num3 <= 2 ** 31 - 1:
			ret.append(str(num3))
			return True
		if self.validFib(S, n2, n3, i + len(n3), ret) and num3 <= 2 ** 31 - 1:
			ret.append(str(num3))
			return True
		return False

	def splitIntoFibonacci(self, S: str) -> List[int]:
		ret = []
		i = 0
		while i < len(S):
			j = 1
			while i + j < len(S):
				n1 = S[:i + 1]
				n2 = S[i + 1:i + j + 1]
				if self.validFib(S, n1, n2, i + j + 1, ret):
					ret.append(n2)
					ret.append(n1)
					return reversed(ret)
				j += 1
			i += 1
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		N = 2 ** 31 - 1

		def dfs(s, path, res):
			if not s and len(path) > 2:
				res.append(path)
				return
			for i in range(len(s)):
				if len(s[:i + 1]) != len(str(int(s[:i + 1]))) or int(s[:i + 1]) > N:
					continue
				if len(path) < 2:
					dfs(s[i + 1:], path + [s[:i + 1]], res)
				elif len(path) > 1 and int(s[:i + 1]) == int(path[-1]) + int(path[-2]):
					dfs(s[i + 1:], path + [s[:i + 1]], res)
		(res, ans) = ([], [])
		dfs(S, [], res)
		if not res:
			return []
		for elem in res[0]:
			ans.append(int(elem))
		return ans


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		result = []

		def getStarter():
			arr = []
			for i in range(1, len(S) - 1):
				for j in range(i + 1, len(S)):
					(s1, s2) = (S[:i], S[i:j])
					if s1[0] == '0' and len(s1) > 1 or (s2[0] == '0' and len(s2) > 1):
						continue
					arr.append((int(s1), int(s2), j))
			return arr

		def dfs(arr, start):
			if start == len(S) and len(arr) >= 3:
				result.append(arr)
				return True
			sum = arr[-2] + arr[-1]
			length = len(str(sum))
			nextNum = int(S[start:start + length])
			if 0 <= sum <= mx and nextNum == sum:
				return dfs(arr + [sum], start + length)
		arr = getStarter()
		mx = 2 ** 31 - 1
		for (num1, num2, start) in arr:
			if dfs([num1, num2], start):
				return result
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def getfirst():
			pairs = []
			for i in range(1, len(S) - 2):
				for j in range(i + 1, len(S) - 1):
					pairs.append((i, j))
			return pairs

		def helper(s, e):
			ans = [S[:s], S[s:e]]
			newS = S[e:]
			while newS:
				nex = int(ans[-1]) + int(ans[-2])
				nex = str(nex)
				if int(nex) >= 2 ** 31:
					return
				if newS[:len(nex)] == nex:
					newS = newS[len(nex):]
					ans += (nex,)
				else:
					return
			return ans
		pairs = getfirst()
		for (s, e) in pairs:
			ans = helper(s, e)
			if ans:
				return ans
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		for (i, l) in enumerate(S):
			if str(int(S[:i + 1])) == S[:i + 1]:
				for j in range(i + 1, len(S) - 1):
					if str(int(S[i + 1:j + 1])) == S[i + 1:j + 1]:
						(pre, cur) = (int(S[:i + 1]), int(S[i + 1:j + 1]))
						res = [pre, cur]
						start = j + 1
						while start < len(S):
							nxt = str(pre + cur)
							length = len(nxt)
							if pre + cur <= 2 ** 31 - 1 and S.startswith(nxt, start):
								(pre, cur) = (cur, int(S[start:start + length]))
								res += (cur,)
								start += length
							else:
								break
						else:
							return res
		return []


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		for i in range(len(S)):
			for j in range(len(S)):
				arr = []
				if S[0:i + 1][0] == '0' and len(S[0:i + 1]) >= 2:
					break
				arr.append(int(S[0:i + 1]))
				if S[i + 1:i + j + 1] != '':
					arr.append(int(S[i + 1:i + j + 1]))
				flag = 0
				k = i + j + 1
				while k < len(S):
					if len(arr) > 1:
						val = arr[-1] + arr[-2]
						if k + len(str(val)) > len(S) or str(val) != S[k:k + len(str(val))]:
							flag = 1
							break
						else:
							k += len(str(val))
							arr.append(val)
					else:
						flag = 1
						break
				if flag == 0:
					if len(arr) > 2:
						for i in arr:
							if i < 0 or i > 2 ** 31 - 1:
								return []
						return arr
		if len(arr) <= 2:
			return []
		return arr


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def split(N, s):
			if not s:
				return N
			c = sum(N[-2:])
			if s.startswith(str(c)):
				return split(N + [c], s[len(str(c)):])
		for i in range(1, len(S)):
			for j in range(i + 1, len(S)):
				a = int(S[:i])
				b = int(S[i:j])
				if str(a) == S[:i] and str(b) == S[i:j]:
					ans = split([a, b], S[j:])
					if ans and all((x <= 2 ** 31 - 1 for x in ans)):
						return ans
		return []


class Solution:

	def splitIntoFibonacci(self, s: str) -> List[int]:

		def isTrue(a, b, s):
			if len(str(a) + str(b) + s) != self.n:
				return []
			l = [a, b]
			while True:
				c = str(a + b)
				if int(c) > 2147483647:
					return []
				l.append(int(c))
				if c == s[:len(c)]:
					a = b
					b = int(c)
					s = s[len(c):]
					if s == '':
						return l
				else:
					return []
		self.n = len(s)
		for i in range(1, len(s)):
			for j in range(i):
				l = isTrue(int(s[0:j + 1]), int(s[j + 1:i + 1]), s[i + 1:])
				if l:
					return l
		return []


class Solution:

	def get_num(self, S, i, j, cache):
		if i == j:
			return int(S[i])
		key = '{}-{}'.format(i, j)
		if key in cache:
			return cache[key]
		v = int(S[i:j + 1])
		cache[key] = v
		return v

	def check(self, st, v):
		if v > 2 ** 31 - 1:
			return False
		if len(st) < 2:
			return True
		return st[-2] + st[-1] == v

	def get_st_key(self, st):
		k1 = None
		k2 = None
		ln = len(st)
		if ln == 0:
			pass
		elif ln == 1:
			k1 = st[-1]
		else:
			k1 = st[-1]
			k2 = st[-2]
			if k1 > k2:
				(k1, k2) = (k2, k1)
		return '{}-{}'.format(k1, k2)

	def split(self, S, i, st, res, cache, cache_res):
		ln = len(S)
		if i >= ln:
			if len(st) >= 3:
				res[0] = list(st)
				return True
			return False
		key = self.get_st_key(st)
		if key in cache_res:
			return cache_res[key]
		res_local = False
		if S[i] == '0':
			new_v = 0
			if self.check(st, new_v):
				st.append(new_v)
				res_local = self.split(S, i + 1, st, res, cache, cache_res)
				del st[-1]
		else:
			for j in range(i, len(S)):
				new_v = self.get_num(S, i, j, cache)
				if self.check(st, new_v):
					st.append(new_v)
					res_local = self.split(S, j + 1, st, res, cache, cache_res)
					del st[-1]
					if res_local:
						break
				if len(st) >= 2 and new_v > st[-2] + st[-1]:
					break
		cache_res[key] = res_local
		return res_local

	def solve(self, S):
		res = [None]
		self.split(S, 0, [], res, {}, {})
		if res[0] is None:
			return []
		return res[0]

	def splitIntoFibonacci(self, S: str) -> List[int]:
		return self.solve(S)


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		res = []
		max_len = len(S) // 3 + 1

		def add_fibonacci(x, left):
			temp1 = x[0]
			temp2 = x[1]
			res = None
			res_left = left
			for i in range(len(left)):
				temp3 = int(left[:i + 1])
				if temp3 == temp1 + temp2 and temp3 < 2 ** 31 - 1:
					res = temp3
					res_left = res_left[i + 1:]
					break
				elif temp3 > temp1 + temp2:
					break
			return (res, res_left)
		for i in range(1, max_len + 1):
			c1 = S[0:i]
			if len(c1) > 1 and c1[0] == '0':
				break
			for j in range(i + 1, max_len + i + 1):
				c2 = S[i:j]
				if len(c2) > 1 and c2[0] == '0':
					break
				next_index = j
				left = S[next_index:]
				res.append(int(c1))
				res.append(int(c2))
				while len(left) > 0:
					(temp, left) = add_fibonacci(res[-2:], left)
					if temp is None:
						res.clear()
						break
					res.append(temp)
				if len(res) > 0:
					break
				res.clear()
			if len(res) > 0:
				break
			res.clear()
		return res


class Solution:

	def splitIntoFibonacci(self, S: str) -> List[int]:
		size = len(S)
		if size < 3:
			return []
		INT_MAX = (1 << 31) - 1

		def dfs(start, expect, prev, res):
			if start >= size:
				return len(res) >= 3
			for end in range(start, size):
				number = S[start:end + 1]
				if len(number) > 1 and number[0] == '0':
					break
				num = int(number)
				if num > INT_MAX:
					break
				if num == expect:
					res.append(num)
					if dfs(end + 1, expect + prev, expect, res):
						return True
					else:
						res.pop()
						break
				elif num > expect:
					break
			return False
		for end in range(1, size):
			for mid in range(end):
				if S[0] == '0' and mid != 0:
					continue
				if S[mid + 1] == '0' and end != mid + 1:
					continue
				first = int(S[:mid + 1])
				second = int(S[mid + 1:end + 1])
				res = [first, second]
				if dfs(end + 1, second + first, second, res):
					return res
		return []


class Solution:

	def splitIntoFibonacci(self, S: str):
		max_len = len(S)
		for first_size in range(1, max_len - 1):
			for second_size in range(1, max_len - 1 - first_size):
				res = self.test(S, first_size, second_size)
				if len(res) >= 3 and int(res[-1]) < 2 ** 31 - 1:
					return res
		return []

	def test(self, s, first_size, second_size):
		cursor = 0
		fibo = []
		first_number = int(s[:first_size])
		if first_size != len(str(first_number)):
			return []
		fibo.append(str(first_number))
		cursor += first_size
		second_number = int(s[cursor:cursor + second_size])
		fibo.append(str(second_number))
		cursor += second_size
		while cursor <= len(s) - 1:
			possible_next = first_number + second_number
			len_next = len(str(possible_next))
			next_number = int(s[cursor:cursor + len_next])
			if cursor + len_next > len(s):
				return []
			elif not next_number == possible_next:
				return []
			fibo.append(str(next_number))
			(first_number, second_number) = (second_number, next_number)
			cursor += len_next
		return fibo


class Solution:

	def splitIntoFibonacci(self, s: str) -> List[int]:

		def dfs(start, string, sequence):
			if start == len(string):
				if len(sequence) > 2:
					return sequence
				return None
			num = 0
			for i in range(start, len(string)):
				if i != start and string[start] == '0':
					return None
				num = num * 10 + ord(string[i]) - ord('0')
				if num >= 2 ** 31:
					break
				if len(sequence) > 1 and sequence[-1] + sequence[-2] != num:
					continue
				sequence.append(num)
				seq = dfs(i + 1, string, sequence)
				if seq != None:
					return seq
				sequence.pop()
		for sticks in range(2, len(s)):
			seq = dfs(0, s, [])
			if seq:
				return seq
		return []


class Solution:

	def __init__(self):
		self.res = []

	def splitIntoFibonacci(self, S: str) -> List[int]:

		def helper(pos, temp):
			if pos == len(S):
				if len(temp) > 2:
					self.res = temp[:]
				return
			if S[pos] == '0':
				if len(temp) > 1:
					if temp[-1] + temp[-2] != 0:
						return
				temp.append(0)
				helper(pos + 1, temp)
				temp.pop()
			else:
				for i in range(pos + 1, len(S) + 1):
					curr = int(S[pos:i])
					if len(temp) < 2:
						temp.append(curr)
						helper(i, temp)
						temp.pop()
					else:
						if curr > temp[-1] + temp[-2] or curr > 2 ** 31 - 1:
							return
						if curr == temp[-1] + temp[-2]:
							temp.append(curr)
							helper(i, temp)
							temp.pop()
		helper(0, [])
		return self.res