# 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:

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