Problem statement
Given a digit string and a target, insert binary +, - or * to produce every expression with that value. Keep every digit in its original order. You may leave a gap empty to create a multi-digit operand.
Use ordinary multiplication precedence, without adding parentheses. A single zero is legal; a multi-digit operand beginning with zero is not. For example, 1*0+5 and 10-5 are valid ways to reach 5 from 105, but an expression containing the operand 05 is invalid.
The public statement allows 1–10 digits and a signed 32-bit target. Intermediate operands and arithmetic use long. The input is not a number to rearrange, and this is not a calculator that merely evaluates one supplied expression.
Constraints & requirements
- CONTRACT
- LeetCode: 1≤num.length≤10, digits only, target is a signed 32-bit integer. Use long for operands and intermediate results. A lone 0 is valid, but 05 is not. The first operand has no operator before it.
Examples 3 test cases
Example 1 Case 1
- Input
num="232"; target=8- Output
["2+3*2","2*3+2"]
Multiplication is evaluated before addition; both expressions use all three digits.
Example 2 Case 2
- Input
num="105"; target=5- Output
["1*0+5","10-5"]
10 is a valid joined operand, while 05 must not be generated.
Example 3 Case 3
- Input
num="12"; target=5- Output
[]
12, 1+2, 1-2 and 1*2 do not equal 5.
Hints Optional
01Hint 1
Choose where the next operand ends, not only which operator to insert.
02Hint 2
Carry the evaluated total plus the SIGNED last multiplicative term.
03Hint 3
For multiplication, replace that old term: total-lastTerm+lastTerm*operand. Restore the builder length after each child.
How to think before coding
There are two decisions, not one:
- Where does the next operand end? From the beginning of
232, it could be 2, 23 or 232. - Unless it is the first operand, which operator joins it to the existing expression?
Use an index for the next unused digit. After choosing an operand ending at end, the child starts at end+1. Saving an answer before this index reaches the input length would silently drop digits.
The difficult part is multiplication. A running total alone does not tell us which earlier addition or subtraction must be revised. We need one more piece of state: the signed last multiplicative term.
Brute force: generate expressions, then evaluate
Every gap between digits has four choices: join, +, -, or *. A baseline enumerates these possibilities, rejects leading-zero operands, and evaluates every finished expression with a correct precedence-aware evaluator.
For d digits there are 4^(d−1) gap assignments before filtering. Re-parsing a length-O(d) expression at every leaf gives a straightforward O(d × 4^(d−1)) upper bound.
We still need to explore possible expressions, but we can carry their values while constructing them. This avoids running a separate evaluator over each complete candidate. It does not turn an enumeration problem into a polynomial-time problem.
Intuition: remember the term that multiplication may replace
Think of an evaluated prefix as a sum of signed terms. In 2+3, the total is 5 and the last term is +3. Appending *2 must replace +3 with +6:
newTotal = total − lastTerm + lastTerm × operand
So 5−3+3×2=8, not (2+3)×2=10.
| Appended operation | New total | New last term |
|---|---|---|
+operand |
total+operand |
operand |
-operand |
total-operand |
-operand |
*operand |
total-lastTerm+lastTerm*operand |
lastTerm*operand |
Why is lastTerm signed?
For 1-2, total is -1 and lastTerm is -2. Appending *3 gives -1−(-2)+(-2×3)=-5, which correctly evaluates 1-2*3.
Storing +2 instead loses the subtraction sign. Likewise, after 2*3, the last term is the whole product 6, not just the last operand 3. This is what makes a chain such as 2*3*4 work.
Why treat the first operand differently?
There is no binary operator before the first number. Start its child with total=operand and lastTerm=operand; do not build an artificial leading 0+... expression.
Why break on a leading zero?
If the current operand starts with 0, its one-digit form is legal. Every longer endpoint would still start with that same zero, so none can be valid. A break rejects all those longer forms at once while preserving a lone 0.
Why not prune when total exceeds target?
A later subtraction can reduce the total, and multiplying the final term by zero can change it dramatically. Overshooting is not a safe stopping rule for this problem.
Algorithm
- Carry index, evaluated total, signed last term, a mutable expression builder and the result list.
- If all digits are used, save a String only when total equals target.
- Grow the next operand digit by digit; stop extending a multi-digit leading-zero operand.
- For the first operand, recurse without an operator.
- Otherwise, recurse with addition, subtraction and multiplication using the state updates above.
- After each child, restore the builder to its saved parent length.
Java solution
All arithmetic state is long even though the requested target is int. Ten input digits can form an operand larger than Integer.MAX_VALUE. StringBuilder.append(num,start,end) also lets us append a chosen digit span without constructing a temporary substring.
import java.util.*;
class Solution {
public static List<String> addOperators(String num, int target) {
List<String> result = new ArrayList<>();
if (num == null || num.isEmpty()) return result; // Defensive policy outside the nonempty contract.
buildExpressions(num, target, 0, 0L, 0L, new StringBuilder(), result);
return result; // All matching expressions; their order is not part of the contract.
}
private static void buildExpressions(String num, long target, int index, long total,
long lastTerm, StringBuilder path, List<String> result) {
if (index == num.length()) { // Only complete uses of the digit string may become answers.
if (total == target) result.add(path.toString()); // Snapshot the matching expression.
return; // Never ignore leftover digits or continue past the end.
}
long operand = 0; // Grow a number digit by digit; operands may contain several digits.
int length = path.length(); // Every sibling must restore this same parent prefix.
for (int end = index; end < num.length(); end++) {
if (end > index && num.charAt(index) == '0') break; // Allow 0, forbid 00, 05, etc.
operand = operand * 10 + num.charAt(end) - '0'; // long protects operands/intermediate products.
if (index == 0) { // The first operand has no operator or artificial leading zero.
path.append(num, index, end + 1);
buildExpressions(num, target, end + 1, operand, operand, path, result);
path.setLength(length); // Restore before trying a longer first operand.
continue; // Only later operands choose +, - or *.
}
path.append('+').append(num, index, end + 1);
buildExpressions(num, target, end + 1, total + operand, operand, path, result);
path.setLength(length); // Undo the entire operator-plus-operand, not just one character.
path.append('-').append(num, index, end + 1);
buildExpressions(num, target, end + 1, total - operand, -operand, path, result);
path.setLength(length); // A subtraction stores a SIGNED last term for later multiplication.
path.append('*').append(num, index, end + 1);
long product = lastTerm * operand; // Extend the whole pending multiplication chain.
buildExpressions(num, target, end + 1, total - lastTerm + product, product, path, result);
path.setLength(length); // Put the shared expression back for the next candidate endpoint.
}
}
public static void main(String[] args) {
System.out.println(addOperators("232", 8)); // [2+3*2, 2*3+2]
System.out.println(addOperators("105", 5)); // [1*0+5, 10-5]
System.out.println(addOperators("12", 5)); // []
}
}The complete invocation demonstrates both matching expressions for 232, the joined-operand/zero case 105, and a no-solution input. Result order may vary in a different correct implementation.
Why restore a length, not remove one character?
A branch might append +32, which is three characters, or a first operand such as 232. Deleting only the last digit would leave a damaged prefix. Each call saves the builder’s entry length and restores exactly that boundary after every child.
The integer parameters are passed by value. Restoring the builder does not require manually undoing total or lastTerm: their parent-frame values never changed.
Illustrated dry run
Use num="232",target=8. Both successful expressions are traced, and the remaining joined-operand branches are explicitly grouped rather than presented as consecutive calls on one path.

Read the text transcript
Follow the Java, step by step
Example: num = "232", target = 8
What to track: index points to the next unused digit; total is the evaluated prefix; lastTerm is its signed last multiplicative term. path is shared and restored by saved length. This traces both successful paths and groups the other failed branches.
-
Choose the first operand
Java operationbuildExpressions(num, target, end + 1, operand, operand, path, result);Statechoose "2": index=1; total=2; lastTerm=2; path="2"The first operand has no operator before it. Longer first operands 23 and 232 are other root choices, not omitted digits.
-
Add the next operand 3
Java operationbuildExpressions(num, target, end + 1, total + operand, operand, path, result);Stateindex=2; total=5; lastTerm=3; path="2+3"The whole prefix evaluates to 5, but only its last term 3 may be extended by a later multiplication.
-
Check addition and subtraction leaves
Java operationif (total == target) result.add(path.toString());State2+3+2 → 7; 2+3-2 → 3; index=3 at each leaf; neither savedThese siblings are checked first because the code tries +, then -, then *. The builder is restored to "2+3" after each.
-
Multiply with precedence
Java operationlong product = lastTerm * operand;Stateoperand=2; product=3×2=6; total=5−3+6=8; lastTerm=6; path="2+3*2"Subtract the old last term before adding its replacement. Multiplying total instead would incorrectly produce 10.
-
Save and restore the expression prefix
Java operationpath.setLength(length);Stateleaf saves 2+3*2; caller restores "2+3"; after that subtree, its caller restores "2"Each caller restores its own saved length. The immutable saved String is not shortened by the shared builder’s undo.
-
Finish subtraction siblings, then choose multiplication
Java operationbuildExpressions(num, target, end + 1, total - lastTerm + product, product, path, result);State2-3 siblings all fail target 8; choose 2*3: index=2; total=6; lastTerm=6; path="2*3"A multiplied prefix keeps the entire product as lastTerm so another multiplication can replace the whole chain.
-
Add 2 to save the other answer
Java operationif (total == target) result.add(path.toString());Statepath="2*3+2"; index=3; total=8; lastTerm=2; result=[2+3*2,2*3+2]The final digit was consumed. Enumeration continues instead of returning immediately after the first match.
-
Complete joined-operand branches
Java operationoperand = operand * 10 + num.charAt(end) - '0';State2 with joined 32 gives 34,-30,64; joined 23 with 2 gives 25,21,46; whole 232 gives 232; none equals 8All sixteen choices across the two digit gaps have now been accounted for. No branch may discard a digit or introduce parentheses.
Final result: [2+3*2, 2*3+2]; both use all digits with ordinary precedence.
For a hand trace, give every frame columns for index, total, lastTerm and path length. Before a multiplication child, first calculate the replacement term on paper. On return, restore only that caller’s builder boundary.
Why it works
Value invariant: The carried total is the value of the constructed prefix under ordinary precedence. Addition and subtraction introduce a new signed term. Multiplication replaces exactly the old final term with its product, preserving that invariant.
Coverage: Every legal expression has a unique sequence of operand endpoints and intervening operators. The loops and three operator branches enumerate that sequence. The first operand and leading-zero guard enforce the remaining formatting rules.
Valid saves: A save occurs only after consuming every input digit and matching the target. No result omits digits, reorders them or depends on extra parentheses.
Stable results: The saved value is a String snapshot. Returning and changing the shared builder cannot change earlier answers.
Complexity and alternative approaches
Let d be input length and R the number of returned expressions. Each expression has O(d) characters.
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Generate, then parse each complete candidate | O(d × 4^(d−1)) upper bound | O(d), excluding answers | Simple separation of generation and evaluation; repeated parsing |
| Carry total and signed last term | O(d × 4^(d−1)) conservative upper bound | O(d), excluding answers | No separate per-leaf parse; multiplication handled during construction |
The conservative bounds include expression construction/copying; they do not claim a different exponential class. Returned strings additionally require O(Rd) space. Recursion depth and the builder are both O(d).
Memoizing only (index,total) and discarding repeated states is unsafe: different prefixes can lead to different required output strings, and the next multiplication also depends on lastTerm.
Common mistakes
- Treating multiplication as
total*operand. - Forgetting the negative sign in lastTerm after subtraction.
- Keeping only the last operand rather than the full final product.
- Forbidding a lone zero along with illegal multi-digit leading zeros.
- Trying only one-digit operands, missing expressions such as
10-5. - Saving before every digit is consumed or returning after the first match.
- Pruning an overshoot even though subtraction/zero can still change it.
- Using int for intermediate arithmetic or deleting only one appended character.