Insert Operators Between Digits to Reach a Target Value
Solve this Problemnum and a target, insert '+', '-', and '*' between some of the digits (grouping the rest into multi-digit numbers, never with a leading zero) so the resulting expression, evaluated with standard operator precedence, equals target. Return every distinct expression that works.
Building the expression as a plain string and parsing it from scratch once it's complete works, but re-derives the entire computation — digit by digit, operator by operator — using information the search already had the moment each piece was placed. Carrying the running total (and the value of the most recent term, needed to handle '*' correctly) forward as the expression is built means every finished expression already knows its own value; checking it against the target is one comparison, not a second pass over the string.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ num.length ≤ 8, num consists only of digits '0'–'9' - ◆
-10⁹ ≤ target ≤ 10⁹ - ◆
'+', '-', and '*' may be inserted between digits (never a leading unary sign); standard operator precedence applies (× before + and −) - ◆
A multi-digit operand may never start with '0' (a lone "0" digit is fine) - ◆
Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Build the Full Expression String, Re-Parse It at the End
BruteBuild up the expression purely as a string of characters — extend the current operand by another digit, or close it off with '+', '-', or '*' and start a new one. Only once every digit has been placed does a separate function parse the finished string from the very first character, respecting precedence by first collapsing every '*' pair into a single running term and then summing what's left, to get its value. This finds every valid expression, but re-parses the whole string character by character at every leaf, including all the digits and operators that were already known the moment they were placed.
O(4ⁿ · n)O(4ⁿ · n)1class Solution {
2 public String[] expressionsReachingTarget(String num, int target) {
3 List<String> result = new ArrayList<>();
4 backtrack(num, target, 0, "", result);
5 Collections.sort(result);
6 return result.toArray(new String[0]);
7 }
8
9 private void backtrack(String num, int target, int index, String expr, List<String> result) {
10 if (index == num.length()) {
11 if (evaluate(expr) == target) {
12 result.add(expr);
13 }
14 return;
15 }
16 for (int end = index; end < num.length(); end++) {
17 String piece = num.substring(index, end + 1);
18 if (piece.length() > 1 && piece.charAt(0) == '0') break;
19 if (index == 0) {
20 backtrack(num, target, end + 1, piece, result);
21 } else {
22 backtrack(num, target, end + 1, expr + "+" + piece, result);
23 backtrack(num, target, end + 1, expr + "-" + piece, result);
24 backtrack(num, target, end + 1, expr + "*" + piece, result);
25 }
26 }
27 }
28
29 private long evaluate(String expr) {
30 List<Long> terms = new ArrayList<>();
31 char sign = '+';
32 long num = 0;
33 for (int i = 0; i <= expr.length(); i++) {
34 char c = i < expr.length() ? expr.charAt(i) : '+';
35 if (Character.isDigit(c)) {
36 num = num * 10 + (c - '0');
37 } else {
38 if (sign == '+') terms.add(num);
39 else if (sign == '-') terms.add(-num);
40 else if (sign == '*') terms.set(terms.size() - 1, terms.get(terms.size() - 1) * num);
41 sign = c;
42 num = 0;
43 }
44 }
45 long sum = 0;
46 for (long t : terms) sum += t;
47 return sum;
48 }
49}Optimal — Carry the Running Value Down Incrementally
OptimalTrack two numbers alongside the expression string as it's built: evaluated, the value of the expression so far, and lastOperand, the value of the most recently added term. Adding a piece with '+' or '-' just adjusts evaluated by ±that piece's value. Adding a piece with '*' needs a bit more care — it must combine with the previous term, not add as a separate one — so evaluated first has lastOperand subtracted back out, then lastOperand × the new piece is added in, and lastOperand itself becomes that product. Every full expression already carries its own value by the time it's complete, so checking against target is a single comparison, never a re-parse.
O(4ⁿ)O(n)1class Solution {
2 public String[] expressionsReachingTarget(String num, int target) {
3 List<String> result = new ArrayList<>();
4 backtrack(num, target, 0, "", 0, 0, result);
5 Collections.sort(result);
6 return result.toArray(new String[0]);
7 }
8
9 private void backtrack(String num, int target, int index, String expr, long evaluated, long lastOperand, List<String> result) {
10 if (index == num.length()) {
11 if (evaluated == target) {
12 result.add(expr);
13 }
14 return;
15 }
16 for (int end = index; end < num.length(); end++) {
17 String piece = num.substring(index, end + 1);
18 if (piece.length() > 1 && piece.charAt(0) == '0') break;
19 long value = Long.parseLong(piece);
20 if (index == 0) {
21 backtrack(num, target, end + 1, piece, value, value, result);
22 } else {
23 backtrack(num, target, end + 1, expr + "+" + piece, evaluated + value, value, result);
24 backtrack(num, target, end + 1, expr + "-" + piece, evaluated - value, -value, result);
25 backtrack(num, target, end + 1, expr + "*" + piece, evaluated - lastOperand + lastOperand * value, lastOperand * value, result);
26 }
27 }
28 }
29}