给表达式添加运算符 图解题解
这道题到底在问什么
- 输入
- num="123", target=6
- 输出
- ["1*2*3","1+2+3"]
- 输入
- num="105", target=5
- 输出
- ["1*0+5","10-5"](注意前导零)
- 输入
- num="3456237490", target=9191
- 输出
- [](无解)
最优解：一步一步想明白
- 3记住乘法的诀窍:撤回上一项再乘回去。下面看调用栈一层层展开。
- 4第一段从下标 0 取 "1"(值 1)。它是表达式开头,前面不放符号,直接落地:value=last=1,继续切下一段(从 1)。
- 5在 "1" 后试 + "2":value 由 1 变成 3,新 last=2。递归 dfs(2)。
- 6在 "1+2" 后试 + "3":value 由 3 变成 6,新 last=3。递归 dfs(3)。
- 7走到串尾(i=3)。当前表达式 "1+2+3" 的值是 6,目标是 6:相等,命中,收入答案!
- 8在 "1+2" 后试 - "3":value 由 3 变成 0,新 last=-3(负号要带进 last)。递归 dfs(3)。
- 9走到串尾(i=3)。当前表达式 "1+2-3" 的值是 0,目标是 6:不相等,丢弃这条分支。
- 10在 "1+2" 后试 * "3":乘法优先级靠撤回上一项 last=2 再乘回去:value = 3 - 2 + 2*3 = 7,新 last=6。递归 dfs(3)。
- 11走到串尾(i=3)。当前表达式 "1+2*3" 的值是 7,目标是 6:不相等,丢弃这条分支。
- 12在 "1" 后试 - "2":value 由 1 变成 -1,新 last=-2(负号要带进 last)。递归 dfs(2)。
- 13在 "1-2" 后试 + "3":value 由 -1 变成 2,新 last=3。递归 dfs(3)。
- 14走到串尾(i=3)。当前表达式 "1-2+3" 的值是 2,目标是 6:不相等,丢弃这条分支。
- 15在 "1-2" 后试 - "3":value 由 -1 变成 -4,新 last=-3(负号要带进 last)。递归 dfs(3)。
- 16走到串尾(i=3)。当前表达式 "1-2-3" 的值是 -4,目标是 6:不相等,丢弃这条分支。
- 17在 "1-2" 后试 * "3":乘法优先级靠撤回上一项 last=-2 再乘回去:value = -1 - -2 + -2*3 = -5,新 last=-6。递归 dfs(3)。
- 18走到串尾(i=3)。当前表达式 "1-2*3" 的值是 -5,目标是 6:不相等,丢弃这条分支。
- 19在 "1" 后试 * "2":乘法优先级靠撤回上一项 last=1 再乘回去:value = 1 - 1 + 1*2 = 2,新 last=2。递归 dfs(2)。
- 20在 "1*2" 后试 + "3":value 由 2 变成 5,新 last=3。递归 dfs(3)。
- 21走到串尾(i=3)。当前表达式 "1*2+3" 的值是 5,目标是 6:不相等,丢弃这条分支。
- 22在 "1*2" 后试 - "3":value 由 2 变成 -1,新 last=-3(负号要带进 last)。递归 dfs(3)。
- 23走到串尾(i=3)。当前表达式 "1*2-3" 的值是 -1,目标是 6:不相等,丢弃这条分支。
- 24在 "1*2" 后试 * "3":乘法优先级靠撤回上一项 last=2 再乘回去:value = 2 - 2 + 2*3 = 6,新 last=6。递归 dfs(3)。
- 25走到串尾(i=3)。当前表达式 "1*2*3" 的值是 6,目标是 6:相等,命中,收入答案!
- 26在 "1" 后试 + "23":value 由 1 变成 24,新 last=23。递归 dfs(3)。
- 27走到串尾(i=3)。当前表达式 "1+23" 的值是 24,目标是 6:不相等,丢弃这条分支。
- 28在 "1" 后试 - "23":value 由 1 变成 -22,新 last=-23(负号要带进 last)。递归 dfs(3)。
- 29走到串尾(i=3)。当前表达式 "1-23" 的值是 -22,目标是 6:不相等,丢弃这条分支。
- 30在 "1" 后试 * "23":乘法优先级靠撤回上一项 last=1 再乘回去:value = 1 - 1 + 1*23 = 23,新 last=23。递归 dfs(3)。
- 31走到串尾(i=3)。当前表达式 "1*23" 的值是 23,目标是 6:不相等,丢弃这条分支。
- 32从首段 "1" 出发的所有分支已试完,回到起点,把首段切得更长再试别的切法。
- 33第一段从下标 0 取 "12"(值 12)。它是表达式开头,前面不放符号,直接落地:value=last=12,继续切下一段(从 2)。
- 34在 "12" 后试 + "3":value 由 12 变成 15,新 last=3。递归 dfs(3)。
- 35走到串尾(i=3)。当前表达式 "12+3" 的值是 15,目标是 6:不相等,丢弃这条分支。
- 36在 "12" 后试 - "3":value 由 12 变成 9,新 last=-3(负号要带进 last)。递归 dfs(3)。
- 37走到串尾(i=3)。当前表达式 "12-3" 的值是 9,目标是 6:不相等,丢弃这条分支。
- 38在 "12" 后试 * "3":乘法优先级靠撤回上一项 last=12 再乘回去:value = 12 - 12 + 12*3 = 36,新 last=36。递归 dfs(3)。
- 39走到串尾(i=3)。当前表达式 "12*3" 的值是 36,目标是 6:不相等,丢弃这条分支。
- 40从首段 "12" 出发的所有分支已试完,回到起点,把首段切得更长再试别的切法。
- 41第一段从下标 0 取 "123"(值 123)。它是表达式开头,前面不放符号,直接落地:value=last=123,继续切下一段(从 3)。
- 42走到串尾(i=3)。当前表达式 "123" 的值是 123,目标是 6:不相等,丢弃这条分支。
- 43从首段 "123" 出发的所有分支已试完。首段已切到整串,所有首段切法都试遍了,整棵决策树走完。
- 44所有分支走完,调用栈弹空。命中目标 6 的表达式共 2 个:"1+2+3"、"1*2*3"。回溯走遍每个缝隙的「+、-、*、连数字」四种选择,乘法用「撤回上一项再乘」保证优先级正确。
⚠️ 容易写错的地方
✗ 错：乘法直接 value*cur
✓ 对：value - last + last*cur,新 last=last*cur
乘法优先级高于加减:必须先把上一项 last 从 value 里撤掉,再把 last*cur 补回去。如 "2+3*2",到 *2 时 value=5、last=3,应是 5-3+3*2=8,而非 5*2=10
✗ 错：多位数没跳前导零
✓ 对：j>i 且 num[i]=="0" 时 break
题目不允许 "05"、"012" 这种带前导零的数;段首是 0 时该段只能是单个 "0",不能再往后扩
✗ 错：减法的 last 忘了带负号
✓ 对：放 - 时新 last = -cur
若后面紧跟乘法要撤回上一项,这个「上一项」是被减去的 -cur;写成 +cur 会让后续乘法算错
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
ans = []
def dfs(i, expr, value, last):
if i == len(num):
if value == target:
ans.append(expr)
return
for j in range(i, len(num)):
if j > i and num[i] == '0':
break
cur_s = num[i:j+1]
cur = int(cur_s)
if i == 0:
dfs(j + 1, cur_s, cur, cur)
else:
dfs(j + 1, expr + '+' + cur_s, value + cur, cur)
dfs(j + 1, expr + '-' + cur_s, value - cur, -cur)
dfs(j + 1, expr + '*' + cur_s, value - last + last * cur, last * cur)
dfs(0, '', 0, 0)
return ansC++
#include <string>
#include <vector>
#include <functional>
using namespace std;
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> ans;
function<void(int,string,long long,long long)> dfs = [&](int i, string expr, long long value, long long last) {
if (i == (int)num.size()) { if (value == target) ans.push_back(expr); return; }
for (int j = i; j < (int)num.size(); ++j) {
if (j > i && num[i] == '0') break;
string curS = num.substr(i, j - i + 1);
long long cur = stoll(curS);
if (i == 0) dfs(j + 1, curS, cur, cur);
else {
dfs(j + 1, expr + "+" + curS, value + cur, cur);
dfs(j + 1, expr + "-" + curS, value - cur, -cur);
dfs(j + 1, expr + "*" + curS, value - last + last * cur, last * cur);
}
}
};
dfs(0, "", 0, 0);
return ans;
}
};Java
import java.util.*;
class Solution {
List<String> ans;
String num;
int target;
public List<String> addOperators(String num, int target) {
ans = new ArrayList<>(); this.num = num; this.target = target;
dfs(0, "", 0, 0);
return ans;
}
private void dfs(int i, String expr, long value, long last) {
if (i == num.length()) { if (value == target) ans.add(expr); return; }
for (int j = i; j < num.length(); j++) {
if (j > i && num.charAt(i) == '0') break;
String curS = num.substring(i, j + 1);
long cur = Long.parseLong(curS);
if (i == 0) dfs(j + 1, curS, cur, cur);
else {
dfs(j + 1, expr + "+" + curS, value + cur, cur);
dfs(j + 1, expr + "-" + curS, value - cur, -cur);
dfs(j + 1, expr + "*" + curS, value - last + last * cur, last * cur);
}
}
}
}复杂度
时间
O(n · 4ⁿ)
n 是数字串长度。每两个数字之间有「+、-、*、连成多位数」四种选择,共约 4ⁿ⁻¹ 条分支;每条分支走到底要构造长度约 n 的表达式串,故再乘一个 n,总体 O(n · 4ⁿ)
空间
O(n²)
递归深度最多 n 层;本写法每层都新建一个长度约 O(n) 的 expr 字符串作为参数,一条递归链上同时持有 n 层各 O(n) 的串,故辅助空间 O(n²)(不计输出答案本身)。若改成共享可变 path 并回溯恢复,可降到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 给表达式添加运算符 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 value 和 last 要用 64 位整数(long / long long),用 int 会怎样?+
num 最长 10 位,单段数字可能接近 10 位(如 "9999999999"),再做乘法或累加,中间结果很容易超过 32 位 int 的范围而溢出。虽然题目保证 target 在 int 范围内,但回溯过程中的临时 value 不受这个约束,可能远超。所以 C++、Java 用 long long / long 保存 value 和 last,避免溢出导致误判;Python 整数无限精度,天然不会溢出。
能不能在递归中途剪枝,提前砍掉不可能命中的分支?+
很难做安全的 value 剪枝。常见的「剩余数字之和到不了 target 就返回」是错的:剩余数字还能连成多位数(如 "99" 可当 99,不是 9+9),也能参与乘法把值放大;反过来「当前已超过 target 就返回」也不成立,因为后面可以放减号把值拉回来。要做 value 剪枝必须有严格的上下界证明,本题教学版不展开。真正安全又常用的只有前导零剪枝(段首为 0 时不再扩段)。好在本题数据规模小(n≤10),直接全枚举即可,无需冒险剪枝。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 给表达式添加运算符 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。