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 <= 10
num
consists of only digits.
Expression Add Operators Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> ans;
dfs(num, target, 0, 0, 0, {}, ans);
return ans;
}
private:
string join(const vector<string>& path) {
string joined;
for (const string& s : path)
joined += s;
return joined;
}
// start index, prev value, current evaluated value
void dfs(const string& num, int target, int start, long prev, long eval,
vector<string>&& path, vector<string>& ans) {
if (start == num.length()) {
if (eval == target)
ans.push_back(join(path));
return;
}
for (int i = start; i < num.length(); ++i) {
if (i > start && num[start] == '0')
return;
const string& s = num.substr(start, i - start + 1);
const long curr = stol(s);
if (start == 0) {
path.push_back(s);
dfs(num, target, i + 1, curr, curr, move(path), ans);
path.pop_back();
} else {
for (const string& op : {"+", "-", "*"}) {
path.push_back(op + s);
if (op == "+")
dfs(num, target, i + 1, curr, eval + curr, move(path), ans);
else if (op == "-")
dfs(num, target, i + 1, -curr, eval - curr, move(path), ans);
else
dfs(num, target, i + 1, prev * curr, eval - prev + prev * curr,
move(path), ans);
path.pop_back();
}
}
}
}
};
Java
class Solution {
public List<String> addOperators(String num, int target) {
List<String> ans = new ArrayList<>();
dfs(num, target, 0, 0, 0, new StringBuilder(), ans);
return ans;
}
private void dfs(String num, int target, int s, long prev, long eval, StringBuilder sb,
List<String> ans) {
if (s == num.length()) {
if (eval == target)
ans.add(sb.toString());
return;
}
for (int i = s; i < num.length(); ++i) {
if (i > s && num.charAt(s) == '0')
return;
final long curr = Long.parseLong(num.substring(s, i + 1));
final int length = sb.length();
if (s == 0) { // first num
dfs(num, target, i + 1, curr, curr, sb.append(curr), ans);
sb.setLength(length);
} else {
dfs(num, target, i + 1, curr, eval + curr, sb.append("+").append(curr), ans);
sb.setLength(length);
dfs(num, target, i + 1, -curr, eval - curr, sb.append("-").append(curr), ans);
sb.setLength(length);
dfs(num, target, i + 1, prev * curr, eval - prev + prev * curr, sb.append("*").append(curr),
ans);
sb.setLength(length);
}
}
}
}
Python
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
ans = []
# start index, prev value, current evaluated value
def dfs(start: int, prev: int, eval: int, path: List[str]) -> None:
if start == len(num):
if eval == target:
ans.append(''.join(path))
return
for i in range(start, len(num)):
if i > start and num[start] == '0':
return
s = num[start:i + 1]
curr = int(s)
if start == 0:
path.append(s)
dfs(i + 1, curr, curr, path)
path.pop()
else:
for op in ['+', '-', '*']:
path.append(op + s)
if op == '+':
dfs(i + 1, curr, eval + curr, path)
elif op == '-':
dfs(i + 1, -curr, eval - curr, path)
else:
dfs(i + 1, prev * curr, eval - prev + prev * curr, path)
path.pop()
dfs(0, 0, 0, [])
return ans
Watch Tutorial
Checkout more Solutions here