Split Array into Fibonacci Sequence — LeetCode 842 Python Solution
MediumStringBacktracking
- Problem
- #842
- Pattern
- Backtracking
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given a string of digits num, such as "123456579". We can split it into a Fibonacci-like sequence [123, 456, 579].
Example
- Input
- num = "1101111"
- Output
- [11,0,11,11]
- Explanation
- The output [110, 1, 111] would also be accepted.
Python solution
Python
class Solution:
def splitIntoFibonacci(self, num: str) -> List[int]:
def dfs(i):
if i == n:
return len(ans) > 2
x = 0
for j in range(i, n):
if j > i and num[i] == '0':
break
x = x * 10 + int(num[j])
if x > 2**31 - 1 or (len(ans) > 2 and x > ans[-2] + ans[-1]):
break
if len(ans) < 2 or ans[-2] + ans[-1] == x:
ans.append(x)
if dfs(j + 1):
return True
ans.pop()
return False
n = len(num)
ans = []
dfs(0)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | Exponential (worst case) |
| Space | O(depth) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 842. Split Array into Fibonacci Sequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 842. Split Array into Fibonacci Sequence?
- LeetCode 842. Split Array into Fibonacci Sequence is rated Medium on LeetCode.
- What topics does LeetCode 842. Split Array into Fibonacci Sequence cover?
- LeetCode 842. Split Array into Fibonacci Sequence is tagged String and Backtracking on LeetCode.