Expression Add Operators
Problem
Given a string of digits and a target value, return all expressions you can build by inserting +, −, or * between digits so that the expression evaluates to target. No unary minus, no leading zeros for multi-digit operands.
num = "123", target = 6["1+2+3", "1*2*3"]def add_operators(num, target):
out = []
def dfs(i, expr, value, last):
if i == len(num):
if value == target: out.append(expr)
return
for j in range(i + 1, len(num) + 1):
piece = num[i:j]
if len(piece) > 1 and piece[0] == '0': break
v = int(piece)
if i == 0:
dfs(j, piece, v, v)
else:
dfs(j, expr + '+' + piece, value + v, v)
dfs(j, expr + '-' + piece, value - v, -v)
dfs(j, expr + '*' + piece, value - last + last * v, last * v)
dfs(0, "", 0, 0)
return outfunction addOperators(num, target) {
const out = [];
function dfs(i, expr, value, last) {
if (i === num.length) {
if (value === target) out.push(expr);
return;
}
for (let j = i + 1; j <= num.length; j++) {
const piece = num.slice(i, j);
if (piece.length > 1 && piece[0] === '0') break;
const v = parseInt(piece, 10);
if (i === 0) dfs(j, piece, v, v);
else {
dfs(j, expr + '+' + piece, value + v, v);
dfs(j, expr + '-' + piece, value - v, -v);
dfs(j, expr + '*' + piece, value - last + last * v, last * v);
}
}
}
dfs(0, "", 0, 0);
return out;
}class Solution {
List<String> out = new ArrayList<>();
String num; int target;
public List<String> addOperators(String num, int target) {
this.num = num; this.target = target;
dfs(0, "", 0L, 0L);
return out;
}
void dfs(int i, String expr, long value, long last) {
if (i == num.length()) {
if (value == target) out.add(expr);
return;
}
for (int j = i + 1; j <= num.length(); j++) {
String piece = num.substring(i, j);
if (piece.length() > 1 && piece.charAt(0) == '0') break;
long v = Long.parseLong(piece);
if (i == 0) dfs(j, piece, v, v);
else {
dfs(j, expr + '+' + piece, value + v, v);
dfs(j, expr + '-' + piece, value - v, -v);
dfs(j, expr + '*' + piece, value - last + last * v, last * v);
}
}
}
}vector<string> out;
string num; int target;
void dfs(int i, string expr, long value, long last) {
if (i == (int)num.size()) {
if (value == target) out.push_back(expr);
return;
}
for (int j = i + 1; j <= (int)num.size(); j++) {
string piece = num.substr(i, j - i);
if (piece.size() > 1 && piece[0] == '0') break;
long v = stol(piece);
if (i == 0) dfs(j, piece, v, v);
else {
dfs(j, expr + '+' + piece, value + v, v);
dfs(j, expr + '-' + piece, value - v, -v);
dfs(j, expr + '*' + piece, value - last + last * v, last * v);
}
}
}
vector<string> addOperators(string n, int t) {
out.clear(); num = n; target = t;
dfs(0, "", 0, 0);
return out;
}Explanation
We slide through the digit string and, at each gap, decide how to split off the next number and which operator (+, -, or *) glues it on. A DFS explores all those choices and keeps the expressions that evaluate to target.
The state carried in dfs(i, expr, value, last) is the trick. i is where we are in the string, expr is the text built so far, value is its running result, and last is the most recently added operand (with its sign). We need last to handle multiplication's precedence.
For + and - it's easy: update value by ±v and set last = ±v. For * we can't just multiply the whole running value — multiplication binds tighter. So we undo the last term and redo it multiplied: value - last + last * v, and the new last becomes last * v.
The loop for j in range(i+1, len+1) chooses how many digits the next operand spans. A guard breaks out when a multi-digit piece starts with '0', forbidding leading zeros. At the end of the string, if value == target, we keep expr.
Example: num = "123", target = 6. The path 1+2+3 evaluates to 6, and 1*2*3 also reaches 6 (the * rewrites handle precedence correctly), so both are returned.