-
Notifications
You must be signed in to change notification settings - Fork 116
/
Copy pathexpression_add_operators.cpp
39 lines (38 loc) · 1.33 KB
/
expression_add_operators.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> results;
DFS(num, target, 0, "", 0, " ", 0, results);
return results;
}
void DFS(string& num, int target, int idx, string solution, long long current_val, string pre_op, long long pre_val, vector<string>& results) {
if (current_val == target && idx == num.size()) {
results.push_back(solution);
return;
}
if (idx == num.size()) return;
string n;
long long v = 0;
for (int i = idx; i < num.size(); ++i) {
if (n =="0") {
return;
}
n += num[i];
v = 10*v + num[i] - '0';
if (solution.size() == 0) {
DFS(num, target, i+1, n, v, " ", 0, results);
}else {
DFS(num, target, i+1, solution + "+" + n, current_val + v, "+", v, results);
DFS(num, target, i+1, solution + "-" + n, current_val - v, "-", v, results);
if (pre_op == "+") {
DFS(num, target, i+1, solution + "*" + n, current_val-pre_val+pre_val*v, pre_op, pre_val*v, results);
}else if (pre_op == "-") {
DFS(num, target, i+1, solution + "*" + n, current_val+pre_val-pre_val*v, pre_op, pre_val*v, results);
}else {
DFS(num, target, i+1, solution + "*" + n, current_val*v, "*", v, results);
}
}
}
return;
}
};