在数字间添加加减号使算式等于目标值
哪些公司问过
答案要点
- 回溯:每个数尝试加或减两条分支,到末尾判断是否等于目标
- 只有加减,从左到右累加即可,无需处理优先级
- 状态可视为一棵二叉决策树,叶子数为2^(n-1)
- 非负整数可转成子集和背包:P=(剩余和+target-nums[0])/2
- 背包DP复杂度O(n·P),P非整数或为负时无解
易错点
- 给第一个数也加符号,和题意不一致(那是LC494的设定)
- 转背包时没判断奇偶和负数,导致错误下标
- 需要输出表达式时只计数,没保存路径
面试官常见追问
- 这个题目能用二叉树表示吗?
- 回溯怎么优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。