Expression Add Operators
Hard · Backtracking · Math · String · Backtracking
Problem
You are given a string num of digits and an integer target. Between neighboring digits you may put +, -, * or nothing at all; nothing joins the digits into a longer number. The expression is evaluated with the usual precedence: * before + and -.
Return every expression that evaluates to target, in any order. The digits stay in their order, and no operand may have a leading zero: "05" is not allowed, although "0" alone is.
Examples
Input: num = "124", target = 9 Output: ["1+2*4"]
1 + 2 * 4 = 9, and no other placement gives 9.
Input: num = "105", target = 5 Output: ["1*0+5","10-5"]
1 * 0 + 5 and 10 - 5 both make 5; 1 * 05 is not allowed because of the leading zero.
Input: num = "11", target = 3 Output: []
The only values reachable are 2, 0, 1 and 11.
Constraints
- 1 <= len(num) <= 10
- num consists only of digits
- -2^31 <= target <= 2^31 - 1
Approaches
- Every operator string, evaluated from scratch — time O(n · 4^n), space O(n) besides the output
Follow-up
What if you only need the number of expressions, not the expressions themselves? Building the strings is most of the memory traffic; count instead. The search space is still about 4^(n-1), because the value and last term rarely repeat, so memoization helps little; the problem is exponential by nature.
Related problems
Start free on Cariara · Coding problems · System design studio
