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: []

Accepted

79,133

Submissions

233,892

class Solution {
public:
 
    void helper(string& num, int st, int target,
                long diff, long total, string s, vector<string>& ans) {
     
        if (st == num.size()) {
            if (total == target) {
               ans.push_back(s);
            }
            return;
        }
     
        for (int i = 1; i < num.size() - st + 1; i++) {
            string curStr = num.substr(st, i);
            if (curStr.size() > 1 && curStr[0] == '0') {continue;}
            long curNum = stoll(curStr);
            if (!s.empty()) {
                helper(num, st + i, target, curNum,
                       total + curNum, s + "+" + curStr, ans);
                helper(num, st + i, target, -curNum,
                       total - curNum, s + "-" + curStr, ans);
                helper(num, st + i, target, diff * curNum,
                       (total - diff) + diff * curNum, s + "*" + curStr, ans);
            } else {
                helper(num, st + i, target, curNum, curNum, curStr, ans);
            }
        }
        return;
    }
 
    vector<string> addOperators(string num, int target) {
        vector<string> ans;
        if (num.empty()) {
            return ans;
        }

        helper(num, 0, target, 0, 0, "", ans);
        return ans;
    }
};


============
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> sol;
        helper(num, 0, 0, 0, target, "", sol);
        return sol;
    }
   
    void helper(string num, int idx, long sum, long prevNum, int target,
                string ans, vector<string>& sol) {
        if (idx == num.size()) {
            if (sum == target) {
                sol.push_back(ans);
            }
            return;
        }
       
        for (int i = idx; i < num.size(); i++) {
            string str = num.substr(idx, i - idx + 1);
            if (str.size() > 1 && str[0] == '0') {
                continue;
            }
            long tmp = stoll(str);
            if (ans.empty()) {
                helper(num, i + 1, tmp, tmp, target, str, sol);
            } else {
                helper(num, i + 1, sum + tmp, tmp, target, ans + "+" + str, sol);
                helper(num, i + 1, sum - tmp, -tmp, target, ans + "-" + str, sol);
                helper(num, i + 1, (sum - prevNum) + prevNum * tmp, prevNum * tmp, target, ans + "*" + str, sol);
            }
           
        }
    }
};