- 剑指Offer 10- I. 斐波那契数列（Easy）
- 题解
classSolution:defsplitIntoFibonacci(self,num):ans=[]defbacktrack(idx):# 若已经到达原始字符串的长度，则表示已经拆分完ifidx==len(num):returnlen(ans)>=3curr=0foriinrange(idx,len(num)):# 剪枝情况1：当拆分出来的数长度大于1时，则不能以0开头ifnum[idx]=="0"andi>idx:breakcurr=curr*10+ord(num[i])-ord("0")# 剪枝情况2：若当前值过大，则停止循环ifcurr>2**31-1:break# 若当前ans列表中的元素不到2个 or curr满足斐波拉契条件，则进行回溯iflen(ans)<2orcurr==ans[-2]+ans[-1]:ans.append(curr)ifbacktrack(i+1):returnTrueans.pop()# 剪枝情况3：若列表中已经有2个数，且拆分出来的数已经大于这两个数的和# 此时curr不满足斐波拉契条件，不需要继续拆分eliflen(ans)>2andcurr>ans[-2]+ans[-1]:breakreturnFalsebacktrack(0)# 从第一个数（下标0）开始回溯returnans
