### Leetcode

• Time:O(n4^{n - 1})
• Space:O(n^2)

## 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)
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
``````