Math
String
Backtracking
Description
Given a string num
that contains only digits and an integer target
, return all possibilities to insert the binary operators '+'
, '-'
, and/or '*'
between the digits of num
so that the resultant expression evaluates to the target
value .
Note that operands in the returned expressions should not contain leading zeros.
Example 1:
Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.
Example 2:
Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.
Example 3:
Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.
Constraints:
1 <= num.length <= 10
num
consists of only digits.
-231 <= target <= 231 - 1
Solutions
Solution 1
Python3 Java C#
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 class Solution :
def addOperators ( self , num : str , target : int ) -> List [ str ]:
ans = []
def dfs ( u , prev , curr , path ):
if u == len ( num ):
if curr == target :
ans . append ( path )
return
for i in range ( u , len ( num )):
if i != u and num [ u ] == '0' :
break
next = int ( num [ u : i + 1 ])
if u == 0 :
dfs ( i + 1 , next , next , path + str ( next ))
else :
dfs ( i + 1 , next , curr + next , path + "+" + str ( next ))
dfs ( i + 1 , - next , curr - next , path + "-" + str ( next ))
dfs (
i + 1 ,
prev * next ,
curr - prev + prev * next ,
path + "*" + str ( next ),
)
dfs ( 0 , 0 , 0 , "" )
return ans
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 class Solution {
private List < String > ans ;
private String num ;
private int target ;
public List < String > addOperators ( String num , int target ) {
ans = new ArrayList <> ();
this . num = num ;
this . target = target ;
dfs ( 0 , 0 , 0 , "" );
return ans ;
}
private void dfs ( int u , long prev , long curr , String path ) {
if ( u == num . length ()) {
if ( curr == target ) ans . add ( path );
return ;
}
for ( int i = u ; i < num . length (); i ++ ) {
if ( i != u && num . charAt ( u ) == '0' ) {
break ;
}
long next = Long . parseLong ( num . substring ( u , i + 1 ));
if ( u == 0 ) {
dfs ( i + 1 , next , next , path + next );
} else {
dfs ( i + 1 , next , curr + next , path + "+" + next );
dfs ( i + 1 , - next , curr - next , path + "-" + next );
dfs ( i + 1 , prev * next , curr - prev + prev * next , path + "*" + next );
}
}
}
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109 using System ;
using System.Collections.Generic ;
public class Expression
{
public long Value ;
public override string ToString ()
{
return Value . ToString ();
}
}
public class BinaryExpression : Expression
{
public char Operator ;
public Expression LeftChild ;
public Expression RightChild ;
public override string ToString ()
{
return string . Format ( "{0}{1}{2}" , LeftChild , Operator , RightChild );
}
}
public class Solution {
public IList < string > AddOperators ( string num , int target ) {
var results = new List < string > ();
if ( string . IsNullOrEmpty ( num )) return results ;
this . num = num ;
this . results = new List < Expression > [ num . Length , num . Length , 3 ];
foreach ( var ex in Search ( 0 , num . Length - 1 , 0 ))
{
if ( ex . Value == target )
{
results . Add ( ex . ToString ());
}
}
return results ;
}
private string num ;
private List < Expression > [,,] results ;
private List < Expression > Search ( int left , int right , int level )
{
if ( results [ left , right , level ] != null )
{
return results [ left , right , level ];
}
var result = new List < Expression > ();
if ( level < 2 )
{
for ( var i = left + 1 ; i <= right ; ++ i )
{
List < Expression > leftResult , rightResult ;
leftResult = Search ( left , i - 1 , level );
rightResult = Search ( i , right , level + 1 );
foreach ( var l in leftResult )
{
foreach ( var r in rightResult )
{
var newObjects = new List < Tuple < char , long >> ();
if ( level == 0 )
{
newObjects . Add ( Tuple . Create ( '+' , l . Value + r . Value ));
newObjects . Add ( Tuple . Create ( '-' , l . Value - r . Value ));
}
else
{
newObjects . Add ( Tuple . Create ( '*' , l . Value * r . Value ));
}
foreach ( var newObject in newObjects )
{
result . Add ( new BinaryExpression
{
Value = newObject . Item2 ,
Operator = newObject . Item1 ,
LeftChild = l ,
RightChild = r
});
}
}
}
}
}
else
{
if ( left == right || num [ left ] != '0' )
{
long x = 0 ;
for ( var i = left ; i <= right ; ++ i )
{
x = x * 10 + num [ i ] - '0' ;
}
result . Add ( new Expression
{
Value = x
});
}
}
if ( level < 2 )
{
result . AddRange ( Search ( left , right , level + 1 ));
}
return results [ left , right , level ] = result ;
}
}
GitHub