String
Backtracking
Description
An additive number is a string whose digits can form an additive sequence .
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits, return true
if it is an additive number or false
otherwise.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03
or 1, 02, 3
is invalid.
Example 1:
Input: "112358"
Output: true
Explanation:
The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
Example 2:
Input: "199100199"
Output: true
Explanation:
The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Constraints:
1 <= num.length <= 35
num
consists only of digits.
Follow up: How would you handle overflow for very large input integers?
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 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 False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 class Solution {
public boolean isAdditiveNumber ( String num ) {
int n = num . length ();
for ( int i = 1 ; i < Math . min ( n - 1 , 19 ); ++ i ) {
for ( int j = i + 1 ; j < Math . min ( n , i + 19 ); ++ j ) {
if ( i > 1 && num . charAt ( 0 ) == '0' ) {
break ;
}
if ( j - i > 1 && num . charAt ( i ) == '0' ) {
continue ;
}
long a = Long . parseLong ( num . substring ( 0 , i ));
long b = Long . parseLong ( num . substring ( i , j ));
if ( dfs ( a , b , num . substring ( j ))) {
return true ;
}
}
}
return false ;
}
private boolean dfs ( long a , long b , String num ) {
if ( "" . equals ( num )) {
return true ;
}
if ( a + b > 0 && num . charAt ( 0 ) == '0' ) {
return false ;
}
for ( int i = 1 ; i < Math . min ( num . length () + 1 , 19 ); ++ i ) {
if ( a + b == Long . parseLong ( num . substring ( 0 , i ))) {
if ( dfs ( b , a + b , num . substring ( i ))) {
return true ;
}
}
}
return false ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 class Solution {
public :
bool isAdditiveNumber ( string num ) {
int n = num . size ();
for ( int i = 1 ; i < min ( n - 1 , 19 ); ++ i ) {
for ( int j = i + 1 ; j < min ( n , i + 19 ); ++ j ) {
if ( i > 1 && num [ 0 ] == '0' ) break ;
if ( j - i > 1 && num [ i ] == '0' ) continue ;
auto a = stoll ( num . substr ( 0 , i ));
auto b = stoll ( num . substr ( i , j - i ));
if ( dfs ( a , b , num . substr ( j , n - j ))) return true ;
}
}
return false ;
}
bool dfs ( long long a , long long b , string num ) {
if ( num == "" ) return true ;
if ( a + b > 0 && num [ 0 ] == '0' ) return false ;
for ( int i = 1 ; i < min (( int ) num . size () + 1 , 19 ); ++ i )
if ( a + b == stoll ( num . substr ( 0 , i )))
if ( dfs ( b , a + b , num . substr ( i , num . size () - i )))
return true ;
return false ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 func isAdditiveNumber ( num string ) bool {
n := len ( num )
var dfs func ( a , b int64 , num string ) bool
dfs = func ( a , b int64 , num string ) bool {
if num == "" {
return true
}
if a + b > 0 && num [ 0 ] == '0' {
return false
}
for i := 1 ; i < min ( len ( num ) + 1 , 19 ); i ++ {
c , _ := strconv . ParseInt ( num [: i ], 10 , 64 )
if a + b == c {
if dfs ( b , c , num [ i :]) {
return true
}
}
}
return false
}
for i := 1 ; i < min ( n - 1 , 19 ); i ++ {
for j := i + 1 ; j < min ( n , i + 19 ); j ++ {
if i > 1 && num [ 0 ] == '0' {
break
}
if j - i > 1 && num [ i ] == '0' {
continue
}
a , _ := strconv . ParseInt ( num [: i ], 10 , 64 )
b , _ := strconv . ParseInt ( num [ i : j ], 10 , 64 )
if dfs ( a , b , num [ j :]) {
return true
}
}
}
return false
}
GitHub