LeetCode 842. Split Array into Fibonacci Sequence Explanation and Solution

For basic backtracking problems:

English Version:

Chinese Version:

Thanks in advance. :D

Happy coding every day!

[aunnfriends]

dealing with overflow for python is different

class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
rs = []
over_flow = 2 ** 31
def backtracking(rs, pos):
# (a) base case
if pos == len(S):
return len(rs) > 2

# (b) recursive case with a lot of setup
num = 0
for i in range(pos, len(S)):
num = num * 10 + int(S[i])
if num > over_flow: return False
if len(rs) < 2 or rs[-2] + rs[-1] == num:
# 1. choose
rs.append(num)
# 2. recursively explore
if backtracking(rs, i + 1):
return True
# 3. un-choose
rs.pop()
if pos == i and S[i] == '0':
return False
backtracking(rs, 0)
return rs

[reshmadokania]

Can you also mention in your website the time complexity for all the problems.

[amandhaka]

What is logic behind the following code ? Please explain:
if(pos==i && s.charAt(i)=='0') return false