MediumNo. 0842
Split Array into Fibonacci Sequence — LeetCode 842 Python Solution
- Pattern
- Backtracking
- Topics
- String, 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
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
- Time
- Exponential (worst case)
- Space · auxiliary
- O(depth)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0079 | Word Search | Medium |
| 0093 | Restore IP Addresses | Medium |
| 0212 | Word Search II | Hard |
| 0257 | Binary Tree Paths | Easy |
| 0282 | Expression Add Operators | Hard |
| 0301 | Remove Invalid Parentheses | Hard |
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.