

282. Expression Add Operators

Description

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"]

2.

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

3.

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

4.

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

5.

Input: num = "3456237490", target = 9191
Output: []

Java

public List<String> addOperators(String num, int target) {
    List<String> res = new ArrayList<>();
    if(num == null || num.length() == 0) return res;
    helper(num, "", 0, 0, 0, target, res);
    return res;
}
public void helper(String num, String temp, int pos, long cur, long prev, int target, List<String> res) {
    if(pos == num.length()) {
        if(cur == target) {
            res.add(temp);
        }
        return;
    }
    for(int i = pos; i < num.length(); i++) {
        if(i != pos && num.charAt(pos) == '0') break;
        long t = Long.parseLong(num.substring(pos, i + 1));
        if(pos == 0) {
            helper(num, temp + t, i + 1, t, t, target, res);
        }else{
            helper(num, temp + "+" + t, i + 1, cur + t, t, target, res);
            helper(num, temp + "-" + t, i + 1, cur - t, -t, target, res);
            helper(num, temp + "*" + t, i + 1, cur - prev + t * prev, t * prev, target, res);
        }
    }
}

JavaScript

var addOperators = function(num, target) {
    var res = [];
    helper(num, "", 0, 0, 0, target, res);
    return res;
};

function helper(num, temp, pos, cur, prev, target, res) {
    if(pos === num.length) {
        if(cur === target) {
            res.push(temp);
        }
        return;
    }
    for(let i = pos; i < num.length; i++) {
        if(i != pos && num.charAt(pos) == '0') break;
        let n = parseInt(num.substring(pos, i + 1));
        if(pos == 0) {
            helper(num, "" + n, i + 1, n, n, target, res);
        }else{
            helper(num, temp + "+" + n, i + 1, cur + n, n, target, res);
            helper(num, temp + "-" + n, i + 1, cur - n, -n, target, res);
            helper(num, temp + "*" + n, i + 1, cur - prev + n * prev, n * prev, target, res);
        }
    }
}

C++

public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        helper(num, "", 0, 0, 0, target, res);
        return res;
    }
private:
    void helper(string num, string temp, int pos, long cur, long prev, int target, vector<string>& res) {
        if(pos == num.size()) {
            if(cur == target) {
                res.push_back(temp);
            }
            return;
        }
        for(int i = pos; i < num.size(); i++) {
            if(i != pos && num[pos] == '0') break;
            string n = num.substr(pos, i - pos + 1);
            if(pos == 0) {
                helper(num, "" + n, i + 1, stoll(n), stoll(n), target, res);
            }else{
                helper(num, temp + "+" + n, i + 1, cur + stoll(n), stoll(n), target, res);
                helper(num, temp + "-" + n, i + 1, cur - stoll(n), -stoll(n), target, res);
                helper(num, temp + "*" + n, i + 1, cur - prev + prev * stoll(n), prev * stoll(n), target, res);
            }
        }
    }