Additive Number — LeetCode 306 Python Solution
MediumStringBacktracking
- Problem
- #306
- Pattern
- Backtracking
- Reading time
- 4 min
- Source
- leetcode.com
The problem
An additive number is a string whose digits can form an additive sequence. A valid additive sequence should contain at least three numbers.
Example
- Input
- "112358"
- Output
- true
- Explanation
- The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
Python solution
Python
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
def dfs(a, b, num):
if not num:
return True
if a + b > 0 and num[0] == '0':
return False
for i in range(1, len(num) + 1):
if a + b == int(num[:i]):
if dfs(b, a + b, num[i:]):
return True
return False
n = len(num)
for i in range(1, n - 1):
for j in range(i + 1, n):
if i > 1 and num[0] == '0':
break
if j - i > 1 and num[i] == '0':
continue
if dfs(int(num[:i]), int(num[i:j]), num[j:]):
return True
return FalseComplexity
| 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 306. Additive Number 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 306. Additive Number?
- LeetCode 306. Additive Number is rated Medium on LeetCode.
- What topics does LeetCode 306. Additive Number cover?
- LeetCode 306. Additive Number is tagged String and Backtracking on LeetCode.