-
Notifications
You must be signed in to change notification settings - Fork 0
/
282. Expression Add Operators.cpp
27 lines (26 loc) · 1.05 KB
/
282. 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
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));
}
}
}
};