# 282. Expression Add Operators
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
Example 1:
Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]
Example 2:
Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
Example 3:
Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
Example 4:
Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]
Example 5:
Input: num = "3456237490", target = 9191
Output: []
# Solution
Approach 1: Backtracking.
# Code (Python)
Approach 1:
class Solution(object):
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
# http://bookshadow.com/weblog/2015/09/16/leetcode-expression-add-operators/
def isValidNum(string):
return not (string.startswith('00') or (int(string) and string.startswith('0')))
def solve(string, target, mul_expr = '', multiplier = 1):
result = []
if isValidNum(string) and int(string) * multiplier == target:
result.append(string + mul_expr)
for i in range(len(string) - 1): # make sure l_string and r_string both contain at least 1 character
l_string, r_string = string[:i+1], string[i+1:]
if not isValidNum(r_string):
continue
r_expr, r_val = r_string + mul_expr, multiplier * int(r_string)
# add '+' between l and r_string
for solution in solve(l_string, target - r_val):
result.append(solution + '+' + r_expr)
# add '-' between l and r_string
for solution in solve(l_string, target + r_val):
result.append(solution + '-' + r_expr)
# add '*' between l and r_string
for solution in solve(l_string, target, '*' + r_expr, r_val):
result.append(solution)
return result
return [] if not num else solve(num, target)
# Code (C++)
Approach 1:
class Solution {
private:
vector<string> res;
void doAddOperators(string num, int head, int target, long prevNum, char prevOp, string buf) {
for (int tail = head; tail < num.size(); ++tail)
{
if (tail > head && num[head] == '0')
break;
string currStr = num.substr(head, tail-head+1);
long currNum = stol(currStr);
if (prevOp == '-')
currNum = 0 - currNum;
else if (prevOp == '*')
currNum *= prevNum;
if (tail == num.size()-1)
{
if (currNum == target)
res.push_back(buf + currStr);
break;
}
// +
doAddOperators(num, tail+1, target-currNum, currNum, '+', buf + currStr + "+");
// -
doAddOperators(num, tail+1, target-currNum, currNum, '-', buf + currStr + "-");
// *
doAddOperators(num, tail+1, target, currNum, '*', buf + currStr + "*");
}
}
public:
vector<string> addOperators(string num, int target) {
doAddOperators(num, 0, target, 0, '+', "");
return res;
}
};