解题思路:
一道从思路上不是很复杂的回溯题,但是细节拉满,值得注意。
- 首先在回溯中判断是否到达最后一个位置,到达了判断res是否为target,不是则return,是放到ans中;
- 遍历num,一位一位地前进,注意由于不能有前导零的存在,需要进行判断,即固定住头如果是0,那么不能往后遍历;
- 第三步记录下得到的新的数,然后进行加减乘运算;
- 最后for循环结束后回溯,将expr重置为0。
中间其实很多细节,包括传参由于参数过多,可以内置函数或者把参数作为类的属性,代码如下:
class Solution {
private:
int n;
int target;
vector<string> ans;
string num;
public:
vector<string> addOperators(string num, int target) {
n = num.length();
this -> target = target;
this -> num = num;
string expr;
backtrack(expr, 0, 0, 0);
return ans;
}
void backtrack(string& expr, int i, long res, long mul) {
if (i == n) {
if (res == target) {
ans.emplace_back(expr);
}
return;
}
int signIndex = expr.size();
if (i > 0) {
expr.push_back(0); // 占位,下面填充符号
}
long val = 0;
// 枚举截取的数字长度(取多少位),注意数字可以是单个 0 但不能有前导零
for (int j = i; j < n && (j == i || num[i] != '0'); ++j) {
val = val * 10 + num[j] - '0';
expr.push_back(num[j]);
if (i == 0) { // 表达式开头不能添加符号
backtrack(expr, j + 1, val, val);
} else { // 枚举符号
expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val);
expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val);
expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val);
}
}
expr.resize(signIndex);
}
};