Last updated on March 1st, 2025 at 09:08 pm

Here, we see an Expression Add Operators LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Divide and Conquer

Companies

Facebook, Google

Level of Question

Hard

Expression Add Operators LeetCode Solution

1. Problem Statement

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:
Input: num = “123”, target = 6
Output: [“1*2*3″,”1+2+3”]
Explanation: Both “1*2*3” and “1+2+3” evaluate to 6.

Example 2:
Input: num = “232”, target = 8
Output: [“2*3+2″,”2+3*2”]
Explanation: Both “2*3+2” and “2+3*2” evaluate to 8.

Example 3:
Input: num = “3456237490”, target = 9191
Output: []
Explanation: There are no expressions that can be created from “3456237490” to evaluate to 9191.

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Backtracking”. Backtracking is a general algorithmic technique that involves exploring all possible solutions to a problem by incrementally building candidates and abandoning a candidate as soon as it is determined that it cannot lead to a valid solution.

3. Code Implementation in Different Languages

3.1 Expression Add Operators C++

class Solution {
private:
    void dfs(std::vector<string>& res, const string& num, const int target, string cur, int pos, const long cv, const long pv, const char op) {
        if (pos == num.size() && cv == target) {
            res.push_back(cur);
        } else {
            for (int i=pos+1; i<=num.size(); i++) {
                string t = num.substr(pos, i-pos);
                long now = stol(t);
                if (to_string(now).size() != t.size()) continue;
                dfs(res, num, target, cur+'+'+t, i, cv+now, now, '+');
                dfs(res, num, target, cur+'-'+t, i, cv-now, now, '-');
                dfs(res, num, target, cur+'*'+t, i, (op == '-') ? cv+pv - pv*now : ((op == '+') ? cv-pv + pv*now : pv*now), pv*now, op);
            }
        }
    }

public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        if (num.empty()) return res;
        for (int i=1; i<=num.size(); i++) {
            string s = num.substr(0, i);
            long cur = stol(s);
            if (to_string(cur).size() != s.size()) continue;
            dfs(res, num, target, s, i, cur, cur, '#');
        }
        return res;
    }
};

3.2 Expression Add Operators Java

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

3.3 Expression Add Operators JavaScript

var addOperators = function(num, target) {
    const output = []
    function permute(str, arr, total, prev) {
        if(!str.length && total === target) output.push(arr.join(''));
        let len = str.length;
        if(str[0] === '0') len = 1;
        for(let i = 1; i <= len; i++) {
            const curr = +str.slice(0, i);
            const rest = str.slice(i);
            if(!arr.length) permute(rest, [curr], curr, curr);
            else {
                permute(rest, [...arr, '+', curr], total+curr, curr);
                permute(rest, [...arr, '-', curr], total-curr, 0-curr);
                const prod = prev * curr;
                permute(rest, [...arr, '*', curr], total-prev+prod, prod);
            }
        }
    }
    permute(num, [], 0, 0);
    return output;
};

3.4 Expression Add Operators Python

class Solution(object):
    def addOperators(self, num, target):
        res, self.target = [], target
        for i in range(1,len(num)+1):
            if i == 1 or (i > 1 and num[0] != "0"):
                self.dfs(num[i:], num[:i], int(num[:i]), int(num[:i]), res)
        return res
    def dfs(self, num, temp, cur, last, res):
        if not num:
            if cur == self.target:
                res.append(temp)
            return
        for i in range(1, len(num)+1):
            val = num[:i]
            if i == 1 or (i > 1 and num[0] != "0"):
                self.dfs(num[i:], temp + "+" + val, cur+int(val), int(val), res)
                self.dfs(num[i:], temp + "-" + val, cur-int(val), -int(val), res)
                self.dfs(num[i:], temp + "*" + val, cur-last+last*int(val), last*int(val), res)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n * 3^n-1)	O(n * 3^n-1)
Java	O(n * 3^n-1)	O(n * 3^n-1)
JavaScript	O(n * 3^n-1)	O(n * 3^n-1)
Python	O(n * 3^n-1)	O(n * 3^n-1)

The time complexity is exponential due to the combinatorial nature of the problem.
The space complexity includes both the recursion stack and the storage for results.
The implementation in all languages follows the same backtracking approach, with minor syntactic differences.