# Expression Add Operators LeetCode Solution

Here, We see Expression Add Operators LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

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

## Expression Add Operators LeetCode SolutionC++

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;
}
};Code language: PHP (php)

## Expression Add Operators LeetCode SolutionJava

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)
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 );
}
}
}
}Code language: JavaScript (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;
};Code language: JavaScript (javascript)

class Solution(object):
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)
Scroll to Top