Insert Operators Between Digits to Reach a Target Value

Implement expressionsReachingTarget

Given a string of digits num 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.

Example 1:

Input: num = "1213", target = 5

Output: ["1*2*1+3","1*2+1*3","1+2-1+3"]

Example 2:

Input: num = "8", target = 8

Output: ["8"]

Example 3:

Input: num = "4790", target = 21

Output: []

+ 4 hidden test cases run on Submit.

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

num =

1213

target =

5