题目描述
思路解析动画文字版
记住乘法的诀窍:撤回上一项再乘回去。下面看调用栈一层层展开。
第一段从下标 0 取 "1"(值 1)。它是表达式开头,前面不放符号,直接落地:value=last=1,继续切下一段(从 1)。
在 "1" 后试 + "2":value 由 1 变成 3,新 last=2。递归 dfs(2)。
在 "1+2" 后试 + "3":value 由 3 变成 6,新 last=3。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1+2+3" 的值是 6,目标是 6:相等,命中,收入答案!
在 "1+2" 后试 - "3":value 由 3 变成 0,新 last=-3(负号要带进 last)。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1+2-3" 的值是 0,目标是 6:不相等,丢弃这条分支。
在 "1+2" 后试 * "3":乘法优先级靠撤回上一项 last=2 再乘回去:value = 3 - 2 + 2*3 = 7,新 last=6。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1+2*3" 的值是 7,目标是 6:不相等,丢弃这条分支。
在 "1" 后试 - "2":value 由 1 变成 -1,新 last=-2(负号要带进 last)。递归 dfs(2)。
在 "1-2" 后试 + "3":value 由 -1 变成 2,新 last=3。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1-2+3" 的值是 2,目标是 6:不相等,丢弃这条分支。
在 "1-2" 后试 - "3":value 由 -1 变成 -4,新 last=-3(负号要带进 last)。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1-2-3" 的值是 -4,目标是 6:不相等,丢弃这条分支。
在 "1-2" 后试 * "3":乘法优先级靠撤回上一项 last=-2 再乘回去:value = -1 - -2 + -2*3 = -5,新 last=-6。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1-2*3" 的值是 -5,目标是 6:不相等,丢弃这条分支。
在 "1" 后试 * "2":乘法优先级靠撤回上一项 last=1 再乘回去:value = 1 - 1 + 1*2 = 2,新 last=2。递归 dfs(2)。
在 "1*2" 后试 + "3":value 由 2 变成 5,新 last=3。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1*2+3" 的值是 5,目标是 6:不相等,丢弃这条分支。
在 "1*2" 后试 - "3":value 由 2 变成 -1,新 last=-3(负号要带进 last)。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1*2-3" 的值是 -1,目标是 6:不相等,丢弃这条分支。
在 "1*2" 后试 * "3":乘法优先级靠撤回上一项 last=2 再乘回去:value = 2 - 2 + 2*3 = 6,新 last=6。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1*2*3" 的值是 6,目标是 6:相等,命中,收入答案!
在 "1" 后试 + "23":value 由 1 变成 24,新 last=23。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1+23" 的值是 24,目标是 6:不相等,丢弃这条分支。
在 "1" 后试 - "23":value 由 1 变成 -22,新 last=-23(负号要带进 last)。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1-23" 的值是 -22,目标是 6:不相等,丢弃这条分支。
在 "1" 后试 * "23":乘法优先级靠撤回上一项 last=1 再乘回去:value = 1 - 1 + 1*23 = 23,新 last=23。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "1*23" 的值是 23,目标是 6:不相等,丢弃这条分支。
从首段 "1" 出发的所有分支已试完,回到起点,把首段切得更长再试别的切法。
第一段从下标 0 取 "12"(值 12)。它是表达式开头,前面不放符号,直接落地:value=last=12,继续切下一段(从 2)。
在 "12" 后试 + "3":value 由 12 变成 15,新 last=3。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "12+3" 的值是 15,目标是 6:不相等,丢弃这条分支。
在 "12" 后试 - "3":value 由 12 变成 9,新 last=-3(负号要带进 last)。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "12-3" 的值是 9,目标是 6:不相等,丢弃这条分支。
在 "12" 后试 * "3":乘法优先级靠撤回上一项 last=12 再乘回去:value = 12 - 12 + 12*3 = 36,新 last=36。递归 dfs(3)。
走到串尾(i=3)。当前表达式 "12*3" 的值是 36,目标是 6:不相等,丢弃这条分支。
从首段 "12" 出发的所有分支已试完,回到起点,把首段切得更长再试别的切法。
第一段从下标 0 取 "123"(值 123)。它是表达式开头,前面不放符号,直接落地:value=last=123,继续切下一段(从 3)。
走到串尾(i=3)。当前表达式 "123" 的值是 123,目标是 6:不相等,丢弃这条分支。
从首段 "123" 出发的所有分支已试完。首段已切到整串,所有首段切法都试遍了,整棵决策树走完。
所有分支走完,调用栈弹空。命中目标 6 的表达式共 2 个:"1+2+3"、"1*2*3"。回溯走遍每个缝隙的「+、-、*、连数字」四种选择,乘法用「撤回上一项再乘」保证优先级正确。
边界:单 0 直接命中;"00" 三种符号都成立;无解返回空。
两个延伸:64 位防溢出;乘法导致难以简单剪枝。
参考代码
from typing import Listclass 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 ans复杂度
- 时间：O(n · 4ⁿ)，n 是数字串长度。每两个数字之间有「+、-、*、连成多位数」四种选择,共约 4ⁿ⁻¹ 条分支;每条分支走到底要构造长度约 n 的表达式串,故再乘一个 n,总体 O(n · 4ⁿ)
- 空间：O(n²)，递归深度最多 n 层;本写法每层都新建一个长度约 O(n) 的 expr 字符串作为参数,一条递归链上同时持有 n 层各 O(n) 的串,故辅助空间 O(n²)(不计输出答案本身)。若改成共享可变 path 并回溯恢复,可降到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么 value 和 last 要用 64 位整数(long / long long),用 int 会怎样?
追问能不能在递归中途剪枝,提前砍掉不可能命中的分支?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
不同路径 III
LeetCode 980 · 困难 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题