## # 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):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
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)
{
break;
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;
}
};
``````