Algorithm
Problem Name: 282. Expression Add Operators
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.
Constraints:
1 <= num.length <= 10numconsists of only digits.-231 <= target <= 231 - 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
char **p;
int sz;
int n;
} res_t;
int str2int(char *num, int l) {
int k, i;
k = 0;
while (l -- > 0) {
i = *num - '0';
if (k > 214748364 ||
(k == 214748364 && i > 7)) {
return -1;
}
k = k * 10 + i;
num ++;
}
return k;
}
void add2res(char *buff, res_t *res) {
if (res->sz == res->n) {
res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(char *));
//assert(res->p);
}
res->p[res->n ++] = strdup(buff);
}
void bt(char *num, int s, int e, long n, long m, int target, char *buff, int d, res_t *res) {
int l, k;
if (s == e) { // start == end, done!
if (n == target) {
//printf("%d, %d\n", n, target);
buff[d] = 0;
add2res(buff, res);
}
return;
}
for (l = 1; l < = e - s && l <= 10; l ++) {
if (l > 1 && num[s] == '0') break;
k = str2int(&num[s], l);
if (k == -1) break; // overflow
//printf("%d\n", k);
if (!d) {
strncpy(buff, &num[s], l);
bt(num, s + l, e, k, k, target, buff, l, res);
} else {
strncpy(&buff[d + 1], &num[s], l);
buff[d] = '+';
bt(num, s + l, e, n + k, k, target, buff, d + 1 + l, res);
buff[d] = '-';
bt(num, s + l, e, n - k, -k, target, buff, d + 1 + l, res);
buff[d] = '*';
bt(num, s + l, e, n - m + m * k, m * k, target, buff, d + 1 + l, res);
// m is previous k, n is overall total up to previous k
}
}
}
char** addOperators(char* num, int target, int* returnSize) {
res_t res;
char *buff;
int l;
res.sz = 10;
res.p = malloc(res.sz * sizeof(char *));
//assert(res.p);
res.n = 0;
l = strlen(num);
buff = malloc(l * 2 * sizeof(char));
//assert(buff);
bt(num, 0, l, 0, 0, target, buff, 0, &res);
free(buff);
*returnSize = res.n;
return res.p;
}
Input
num = "123", target = 6
Output
["1*2*3","1+2+3"]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string>res;
backtrack(res, num, target, 0, 0, 0, "");
return res;
}
void backtrack(vector < string>& res, string num, int target, int pos, long sum, long multiply, string path){
if(pos == num.size()){
if(target == sum) res.push_back(path);
return;
}
for(int i = pos; i < num.size(); i++){
if(i != pos && num[pos] == '0') break;
long cur = stol(num.substr(pos, i - pos + 1));
if(pos == 0){
backtrack(res, num, target, i + 1, cur, cur, path + to_string(cur));
}
else{
backtrack(res, num, target, i + 1, sum + cur, cur, path + "+" + to_string(cur));
backtrack(res, num, target, i + 1, sum - cur, -cur, path + "-" + to_string(cur));
backtrack(res, num, target, i + 1, sum - multiply + multiply * cur, multiply * cur, path + "*" + to_string(cur)>;
}
}
}
};
Input
num = "123", target = 6
Output
["1*2*3","1+2+3"]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List addOperators(String num, int target) {
List result = new ArrayList<>();
helper(num, target, "", result, 0, 0, 0);
return result;
}
private void helper(String s, long target, String path, List < String> result, int pos, long calculatedResult, long multed) {
if (pos == s.length()) {
if (calculatedResult == target) {
result.add(new String(path));
}
return;
}
for (int i = pos; i < s.length(); i++) {
if (i != pos && s.charAt(pos) == '0') {
break;
}
long curr = Long.parseLong(s.substring(pos, i + 1));
if (pos == 0) {
helper(s, target, path + curr, result, i + 1, curr, curr);
} else {
helper(s, target, path + "+" + curr, result, i + 1, calculatedResult + curr, curr);
helper(s, target, path + "-" + curr, result, i + 1, calculatedResult - curr, -curr);
helper(s, target, path + "*" + curr, result, i + 1, calculatedResult - multed + multed * curr, multed * curr);
}
}
}
}
Input
num = "232", target = 8
Output
["2*3+2","2+3*2"]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const addOperators = function(num, target) {
let res = [];
let n = num.length;
function recursive(k, str, add, mul, last) {
let sum = add + mul * last;
if (k === n) {
if (sum === target) {
res.push(str);
}
return;
}
let x = num[k] - "0";
if (last !== 0) {
recursive(k + 1, str + num[k], add, mul, last * 10 + x);
}
recursive(k + 1, str + "*" + num[k], add, mul * last, x);
recursive(k + 1, str + "+" + num[k], sum, 1, x);
recursive(k + 1, str + "-" + num[k], sum, -1, x);
}
if (n) recursive(1, num[0], 0, 1, num[0] - "0");
return res;
};
Input
num = "232", target = 8
Output
["2*3+2","2+3*2"]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
# s, val, cur, coeff
q = {("", 0, 0, 1)}
for i, c in enumerate(num):
new = set()
for s, val, cur, coeff in q:
if i:
new.add((s + "+" + c, val + int(c), int(c), 1))
new.add((s + "-" + c, val - int(c), int(c), -1))
new.add((s + "*" + c, val + cur * coeff * (int(c) - 1), int(c), cur * coeff))
if s and s[-1] == "0" and cur == 0: continue
pre = cur
cur = cur * 10 + int(c)
new.add((s + c, val + coeff * (cur - pre), cur, coeff))
q = new
return [s for s, val, cur, coeff in q if val == target]
Input
num = "3456237490", target = 9191
Output
[]