题目来源
给一个数字字符串和一个target，问是否能够用+,-,*三种操作将字符串组合成target。
想了会实在不知道怎么进行划分，乘号的比较麻烦，如果只是加减的话应该还好一些。
代码如下：
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> res;
calResult(num, target, res, 0, 0, "", 0);
return res;
}
void calResult(string num, int target, vector<string> &res, int pos, long long eval, string path, long long multed)
{
if (pos == num.size()) {
if (target == eval)
res.push_back(path);
return;
}
long long len = num.size(), cur = 0;
for (long long i=pos; i<len; i++) {
cur = cur * 10 + num[i] - '0';
if (i != pos && num[pos] == '0')
break;
if (pos == 0) {
calResult(num, target, res, i + 1, cur, to_string(cur), cur);
}
else {
calResult(num, target, res, i + 1, eval + cur, path + "+" + to_string(cur), cur);
calResult(num, target, res, i + 1, eval - cur, path + "-" + to_string(cur), -cur);
calResult(num, target, res, i + 1, eval - multed + multed * cur, path + "*" + to_string(cur), multed * cur);
}
}
}
};
主要有两点值得学习，一是记录上一个multed用来处理乘法操作。另一个是当某个数首字符是0的话就break。
