LeetCode 282: Expression Add Operators (Backtracking with Running Total and Last Operand)
LeetCode 282BacktrackingStringToday we solve LeetCode 282 - Expression Add Operators.
Source: https://leetcode.com/problems/expression-add-operators/
English
Problem Summary
Given a numeric string num and an integer target, insert operators +, -, or * between digits so the resulting expression evaluates to target. Return all valid expressions.
Key Insight
Use DFS to cut the string into operands. Track two values while building the expression: current evaluated total eval and the value of the previous operand prev. For multiplication, undo the previous operand and apply multiplied value: eval - prev + prev * cur.
Algorithm
- Try every possible next operand by extending substring num[index..i].
- Skip numbers with leading zero (except "0").
- If this is the first operand, start expression directly.
- Otherwise branch into +, -, * and recurse.
- When index reaches end, collect expression if eval == target.
Complexity Analysis
Time: exponential, roughly O(4^n) in the worst case due to split/operator branching.
Space: O(n) recursion depth (excluding output size).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public List<String> addOperators(String num, int target) {
List<String> ans = new ArrayList<>();
dfs(num, target, 0, 0L, 0L, new StringBuilder(), ans);
return ans;
}
private void dfs(String num, int target, int idx, long eval, long prev,
StringBuilder expr, List<String> ans) {
if (idx == num.length()) {
if (eval == target) ans.add(expr.toString());
return;
}
int len = expr.length();
long cur = 0;
for (int i = idx; i < num.length(); i++) {
if (i > idx && num.charAt(idx) == '0') break;
cur = cur * 10 + (num.charAt(i) - '0');
String s = num.substring(idx, i + 1);
if (idx == 0) {
expr.append(s);
dfs(num, target, i + 1, cur, cur, expr, ans);
expr.setLength(len);
} else {
expr.append('+').append(s);
dfs(num, target, i + 1, eval + cur, cur, expr, ans);
expr.setLength(len);
expr.append('-').append(s);
dfs(num, target, i + 1, eval - cur, -cur, expr, ans);
expr.setLength(len);
expr.append('*').append(s);
dfs(num, target, i + 1, eval - prev + prev * cur, prev * cur, expr, ans);
expr.setLength(len);
}
}
}
}func addOperators(num string, target int) []string {
res := []string{}
var dfs func(idx int, eval, prev int64, expr string)
dfs = func(idx int, eval, prev int64, expr string) {
if idx == len(num) {
if eval == int64(target) {
res = append(res, expr)
}
return
}
var cur int64 = 0
for i := idx; i < len(num); i++ {
if i > idx && num[idx] == '0' {
break
}
cur = cur*10 + int64(num[i]-'0')
s := num[idx : i+1]
if idx == 0 {
dfs(i+1, cur, cur, s)
} else {
dfs(i+1, eval+cur, cur, expr+"+"+s)
dfs(i+1, eval-cur, -cur, expr+"-"+s)
dfs(i+1, eval-prev+prev*cur, prev*cur, expr+"*"+s)
}
}
}
dfs(0, 0, 0, "")
return res
}class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> ans;
string expr;
dfs(num, target, 0, 0, 0, expr, ans);
return ans;
}
void dfs(const string& num, int target, int idx, long long eval, long long prev,
string& expr, vector<string>& ans) {
if (idx == (int)num.size()) {
if (eval == target) ans.push_back(expr);
return;
}
long long cur = 0;
int len = expr.size();
for (int i = idx; i < (int)num.size(); i++) {
if (i > idx && num[idx] == '0') break;
cur = cur * 10 + (num[i] - '0');
string s = num.substr(idx, i - idx + 1);
if (idx == 0) {
expr += s;
dfs(num, target, i + 1, cur, cur, expr, ans);
expr.resize(len);
} else {
expr += "+" + s;
dfs(num, target, i + 1, eval + cur, cur, expr, ans);
expr.resize(len);
expr += "-" + s;
dfs(num, target, i + 1, eval - cur, -cur, expr, ans);
expr.resize(len);
expr += "*" + s;
dfs(num, target, i + 1, eval - prev + prev * cur, prev * cur, expr, ans);
expr.resize(len);
}
}
}
};from typing import List
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
ans: List[str] = []
def dfs(idx: int, expr: str, eval_val: int, prev: int) -> None:
if idx == len(num):
if eval_val == target:
ans.append(expr)
return
cur = 0
for i in range(idx, len(num)):
if i > idx and num[idx] == '0':
break
cur = cur * 10 + int(num[i])
s = num[idx:i+1]
if idx == 0:
dfs(i + 1, s, cur, cur)
else:
dfs(i + 1, expr + "+" + s, eval_val + cur, cur)
dfs(i + 1, expr + "-" + s, eval_val - cur, -cur)
dfs(i + 1, expr + "*" + s, eval_val - prev + prev * cur, prev * cur)
dfs(0, "", 0, 0)
return ansvar addOperators = function(num, target) {
const ans = [];
const dfs = (idx, expr, evalVal, prev) => {
if (idx === num.length) {
if (evalVal === target) ans.push(expr);
return;
}
let cur = 0;
for (let i = idx; i < num.length; i++) {
if (i > idx && num[idx] === '0') break;
cur = cur * 10 + (num.charCodeAt(i) - 48);
const s = num.slice(idx, i + 1);
if (idx === 0) {
dfs(i + 1, s, cur, cur);
} else {
dfs(i + 1, expr + '+' + s, evalVal + cur, cur);
dfs(i + 1, expr + '-' + s, evalVal - cur, -cur);
dfs(i + 1, expr + '*' + s, evalVal - prev + prev * cur, prev * cur);
}
}
};
dfs(0, '', 0, 0);
return ans;
};中文
题目概述
给你一个数字字符串 num 和目标值 target，在数字之间插入 +、-、*，让表达式计算结果等于 target，返回所有可行表达式。
核心思路
使用 DFS 回溯枚举每一段数字切分。递归中维护当前表达式值 eval 与上一个操作数 prev。处理乘法时，用 eval - prev + prev * cur 修正优先级，不需要真正建表达式树。
算法步骤
- 从当前位置不断扩展出下一个数字片段。
- 若出现前导零（如 "05"）直接剪枝。
- 第一个数字直接放入表达式。
- 后续分别尝试 +、-、* 三种分支继续递归。
- 遍历到末尾时，若 eval == target 就加入答案。
复杂度分析
时间复杂度：指数级，最坏约 O(4^n)。
空间复杂度：O(n)（递归栈，不计输出）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public List<String> addOperators(String num, int target) {
List<String> ans = new ArrayList<>();
dfs(num, target, 0, 0L, 0L, new StringBuilder(), ans);
return ans;
}
private void dfs(String num, int target, int idx, long eval, long prev,
StringBuilder expr, List<String> ans) {
if (idx == num.length()) {
if (eval == target) ans.add(expr.toString());
return;
}
int len = expr.length();
long cur = 0;
for (int i = idx; i < num.length(); i++) {
if (i > idx && num.charAt(idx) == '0') break;
cur = cur * 10 + (num.charAt(i) - '0');
String s = num.substring(idx, i + 1);
if (idx == 0) {
expr.append(s);
dfs(num, target, i + 1, cur, cur, expr, ans);
expr.setLength(len);
} else {
expr.append('+').append(s);
dfs(num, target, i + 1, eval + cur, cur, expr, ans);
expr.setLength(len);
expr.append('-').append(s);
dfs(num, target, i + 1, eval - cur, -cur, expr, ans);
expr.setLength(len);
expr.append('*').append(s);
dfs(num, target, i + 1, eval - prev + prev * cur, prev * cur, expr, ans);
expr.setLength(len);
}
}
}
}func addOperators(num string, target int) []string {
res := []string{}
var dfs func(idx int, eval, prev int64, expr string)
dfs = func(idx int, eval, prev int64, expr string) {
if idx == len(num) {
if eval == int64(target) {
res = append(res, expr)
}
return
}
var cur int64 = 0
for i := idx; i < len(num); i++ {
if i > idx && num[idx] == '0' {
break
}
cur = cur*10 + int64(num[i]-'0')
s := num[idx : i+1]
if idx == 0 {
dfs(i+1, cur, cur, s)
} else {
dfs(i+1, eval+cur, cur, expr+"+"+s)
dfs(i+1, eval-cur, -cur, expr+"-"+s)
dfs(i+1, eval-prev+prev*cur, prev*cur, expr+"*"+s)
}
}
}
dfs(0, 0, 0, "")
return res
}class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> ans;
string expr;
dfs(num, target, 0, 0, 0, expr, ans);
return ans;
}
void dfs(const string& num, int target, int idx, long long eval, long long prev,
string& expr, vector<string>& ans) {
if (idx == (int)num.size()) {
if (eval == target) ans.push_back(expr);
return;
}
long long cur = 0;
int len = expr.size();
for (int i = idx; i < (int)num.size(); i++) {
if (i > idx && num[idx] == '0') break;
cur = cur * 10 + (num[i] - '0');
string s = num.substr(idx, i - idx + 1);
if (idx == 0) {
expr += s;
dfs(num, target, i + 1, cur, cur, expr, ans);
expr.resize(len);
} else {
expr += "+" + s;
dfs(num, target, i + 1, eval + cur, cur, expr, ans);
expr.resize(len);
expr += "-" + s;
dfs(num, target, i + 1, eval - cur, -cur, expr, ans);
expr.resize(len);
expr += "*" + s;
dfs(num, target, i + 1, eval - prev + prev * cur, prev * cur, expr, ans);
expr.resize(len);
}
}
}
};from typing import List
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
ans: List[str] = []
def dfs(idx: int, expr: str, eval_val: int, prev: int) -> None:
if idx == len(num):
if eval_val == target:
ans.append(expr)
return
cur = 0
for i in range(idx, len(num)):
if i > idx and num[idx] == '0':
break
cur = cur * 10 + int(num[i])
s = num[idx:i+1]
if idx == 0:
dfs(i + 1, s, cur, cur)
else:
dfs(i + 1, expr + "+" + s, eval_val + cur, cur)
dfs(i + 1, expr + "-" + s, eval_val - cur, -cur)
dfs(i + 1, expr + "*" + s, eval_val - prev + prev * cur, prev * cur)
dfs(0, "", 0, 0)
return ansvar addOperators = function(num, target) {
const ans = [];
const dfs = (idx, expr, evalVal, prev) => {
if (idx === num.length) {
if (evalVal === target) ans.push(expr);
return;
}
let cur = 0;
for (let i = idx; i < num.length; i++) {
if (i > idx && num[idx] === '0') break;
cur = cur * 10 + (num.charCodeAt(i) - 48);
const s = num.slice(idx, i + 1);
if (idx === 0) {
dfs(i + 1, s, cur, cur);
} else {
dfs(i + 1, expr + '+' + s, evalVal + cur, cur);
dfs(i + 1, expr + '-' + s, evalVal - cur, -cur);
dfs(i + 1, expr + '*' + s, evalVal - prev + prev * cur, prev * cur);
}
}
};
dfs(0, '', 0, 0);
return ans;
};
Comments