282. 给表达式添加运算符
题目描述
输入一个只由数字 0 到 9 组成的字符串 num，以及一个整数 target。
在 num 相邻两个数字之间，可以插入二元运算符 +、-、* 中的一个，也可以什么都不插，让相邻数字连成一个多位数。数字本身的顺序不能变。
找出所有计算结果（乘法优先于加减）等于 target 的写法，以字符串列表返回，顺序不限。表达式里的每个操作数都不能有前导零，例如 05 不合法，但单独的 0 可以。没有符合要求的写法时返回空列表。
示例 1
输入：num = "123", target = 6 输出：["1+2+3","1*2*3"]
解释：1+2+3 和 1*2*3 的值都是 6。
示例 2
输入：num = "232", target = 8 输出：["2+3*2","2*3+2"]
解释：2+3*2 和 2*3+2 的值都是 8。
示例 3
输入：num = "3456237490", target = 9191 输出：[]
解释：没有任何插入方式能得到 9191。
数据范围
1 <= num.length <= 10num只含数字。-2^31 <= target <= 2^31 - 1
解题思路
回溯：dfs(i, expr, val, last) 表示已处理到 num[i]，当前表达式值为 val，最后一个乘法项为 last。枚举下一个操作数 num[i:j]，前导零就 break。加减号直接更新 val；乘号要先撤掉 last 再加上 last·x，因为乘法优先级更高。
为什么正确
val 是 expr 按优先级计算的值，last 是 expr 最后一个加减项（含符号、含其后所有乘法）的值。
复杂度分析
时间 O(n·4^n)：每个间隙有 4 种选择，生成表达式需 O(n)；递归深度 O(n)。
易错点
"05" 这样的操作数不合法，但单独的 "0" 合法；乘号不能直接 val·x，要用 last 修正优先级；中间值会超出 32 位，要用 long。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
res, n = [], len(num)
def dfs(i, expr, val, last):
if i == n:
if val == target:
res.append(expr)
return
for j in range(i + 1, n + 1):
s = num[i:j]
if len(s) > 1 and s[0] == '0':
break
x = int(s)
if i == 0:
dfs(j, s, x, x)
else:
dfs(j, expr + '+' + s, val + x, x)
dfs(j, expr + '-' + s, val - x, -x)
dfs(j, expr + '*' + s, val - last + last * x, last * x)
dfs(0, '', 0, 0)
return resclass Solution {
List<String> res = new ArrayList<>();
String num;
long target;
int n;
public List<String> addOperators(String num, int target) {
this.num = num;
this.target = target;
n = num.length();
dfs(0, "", 0, 0);
return res;
}
void dfs(int i, String expr, long val, long last) {
if (i == n) {
if (val == target) {
res.add(expr);
}
return;
}
for (int j = i + 1; j <= n; j++) {
String s = num.substring(i, j);
if (s.length() > 1 && s.charAt(0) == '0') {
break;
}
long x = Long.parseLong(s);
if (i == 0) {
dfs(j, s, x, x);
} else {
dfs(j, expr + "+" + s, val + x, x);
dfs(j, expr + "-" + s, val - x, -x);
dfs(j, expr + "*" + s, val - last + last * x, last * x);
}
}
}
}class Solution {
vector<string> res;
string num;
long long target;
int n;
void dfs(int i, const string& expr, long long val, long long last) {
if (i == n) {
if (val == target) {
res.push_back(expr);
}
return;
}
for (int j = i + 1; j <= n; j++) {
string s = num.substr(i, j - i);
if (s.size() > 1 && s[0] == '0') {
break;
}
long long x = stoll(s);
if (i == 0) {
dfs(j, s, x, x);
} else {
dfs(j, expr + "+" + s, val + x, x);
dfs(j, expr + "-" + s, val - x, -x);
dfs(j, expr + "*" + s, val - last + last * x, last * x);
}
}
}
public:
vector<string> addOperators(string num, int target) {
this->num = num;
this->target = target;
n = num.size();
dfs(0, "", 0, 0);
return res;
}
};func addOperators(num string, target int) []string {
res, n := []string{}, len(num)
var dfs func(i int, expr string, val, last int)
dfs = func(i int, expr string, val, last int) {
if i == n {
if val == target {
res = append(res, expr)
}
return
}
for j := i + 1; j <= n; j++ {
s := num[i:j]
if len(s) > 1 && s[0] == '0' {
break
}
x := 0
for _, ch := range s {
x = x*10 + int(ch-'0')
}
if i == 0 {
dfs(j, s, x, x)
} else {
dfs(j, expr+"+"+s, val+x, x)
dfs(j, expr+"-"+s, val-x, -x)
dfs(j, expr+"*"+s, val-last+last*x, last*x)
}
}
}
dfs(0, "", 0, 0)
return res
}var addOperators = function(num, target) {
const res = [], n = num.length;
const dfs = (i, expr, val, last) => {
if (i === n) {
if (val === target) {
res.push(expr);
}
return;
}
for (let j = i + 1; j <= n; j++) {
const s = num.slice(i, j);
if (s.length > 1 && s[0] === '0') {
break;
}
const x = Number(s);
if (i === 0) {
dfs(j, s, x, x);
} else {
dfs(j, expr + '+' + s, val + x, x);
dfs(j, expr + '-' + s, val - x, -x);
dfs(j, expr + '*' + s, val - last + last * x, last * x);
}
}
};
dfs(0, '', 0, 0);
return res;
};function addOperators(num: string, target: number): string[] {
const res: string[] = [], n = num.length;
const dfs = (i: number, expr: string, val: number, last: number): void => {
if (i === n) {
if (val === target) {
res.push(expr);
}
return;
}
for (let j = i + 1; j <= n; j++) {
const s = num.slice(i, j);
if (s.length > 1 && s[0] === '0') {
break;
}
const x = Number(s);
if (i === 0) {
dfs(j, s, x, x);
} else {
dfs(j, expr + '+' + s, val + x, x);
dfs(j, expr + '-' + s, val - x, -x);
dfs(j, expr + '*' + s, val - last + last * x, last * x);
}
}
};
dfs(0, '', 0, 0);
return res;
}