Additive Number
Medium · Backtracking · String · Backtracking
Problem
A string of digits is an additive number if it can be cut into a sequence of at least three numbers in which every number after the first two is the sum of the two before it.
No number in the sequence may have a leading zero: "1, 02, 3" is not a valid cut, but a number that is exactly 0 is fine. Given a string num of digits, return true if it is an additive number and false otherwise.
Examples
Input: num = "224610" Output: true
It cuts as 2, 2, 4, 6, 10: each number is the sum of the two before it.
Input: num = "1023" Output: false
No choice of the first two numbers gives a matching rest. "1, 02, 3" would work but 02 has a leading zero.
Input: num = "000" Output: true
0, 0, 0 is valid because 0 + 0 = 0.
Constraints
- 1 <= len(num) <= 35
- num consists only of digits
Approaches
- Backtracking over every next cut — time O(n⁴), space O(n²)
Follow-up
How would you handle overflow if the input were far longer? Adding digit strings costs O(length) per step and never overflows, which is exactly what the Java, C++ and Go versions do.
Related problems
Start free on Cariara · Coding problems · System design studio
