# 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;
    }
};