expression-add-operators

< Previous 　　　　　　　　　　　　　　　　 Next >

282. Expression Add Operators (Hard)

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 = "105", target = 5
Output: ["1*0+5","10-5"]
Explanation: Both "1*0+5" and "10-5" evaluate to 5.
Note that "1-05" is not a valid expression because the 5 has a leading zero.

Example 4:

Input: num = "00", target = 0
Output: ["0*0","0+0","0-0"]
Explanation: "0*0", "0+0", and "0-0" all evaluate to 0.
Note that "00" is not a valid expression because the 0 has a leading zero.

Example 5:

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

Related Topics

[Math] [String] [Backtracking]

Similar Questions

1. Evaluate Reverse Polish Notation (Medium)
2. Basic Calculator (Hard)
3. Basic Calculator II (Medium)
4. Different Ways to Add Parentheses (Medium)
5. Target Sum (Medium)

Hints

Hint 1

Note that a number can contain multiple digits.

Hint 2

Since the question asks us to find all of the valid expressions, we need a way to iterate over all of them. (Hint: Recursion!)

Hint 3

We can keep track of the expression string and evaluate it at the very end. But that would take a lot of time. Can we keep track of the expression's value as well so as to avoid the evaluation at the very end of recursion?

Hint 4

Think carefully about the multiply operator. It has a higher precedence than the addition and subtraction operators.

1 + 2 = 3
1 + 2 - 4 --> 3 - 4 --> -1
1 + 2 - 4 * 12 --> -1 * 12 --> -12 (WRONG!)
1 + 2 - 4 * 12 --> -1 - (-4) + (-4 * 12) --> 3 + (-48) --> -45 (CORRECT!)

Hint 5

We simply need to keep track of the last operand in our expression and reverse it's effect on the expression's value while considering the multiply operator.