Show problems as
Classic problem #282HardMathStringBacktracking

Expression Add Operators

Real-world version: Insert Signs to Hit a Reading
Tracked in this browser only
Read Expression Add Operators on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A paper tape carries the digit run num. A technician writes an arithmetic line by walking the tape from left to right and, in each gap between two neighbouring digits, either writing one of the signs +, -, * or leaving the gap blank. The digits are never reordered and none is dropped.

Digits separated by blank gaps run together into a single number, so the blanks decide how the tape is cut into numbers. A number of two or more digits may not start with 0, though a number that is the single digit 0 is fine.

The line is worth what ordinary arithmetic says it is worth: every * is applied before any + or -, and otherwise the line reads left to right. There are no brackets and no sign in front of the first number.

Return every line worth exactly target, as strings, in any order. Work the arithmetic out yourself rather than handing the text to a built-in expression evaluator.

Examples

Example 1

Input
num = "105", target = 5
Output
["1*0+5", "10-5"]

Both lines are worth 5: in "1*0+5" the product 1*0 is worked out first and 0+5 follows, and "10-5" runs the first two digits together. The cut "1+05" is not allowed because 05 starts with a zero.

Example 2

Input
num = "234", target = 14
Output
["2+3*4"]

"2+3*4" is worth 14 because 3*4 is worked out before the addition. No other way of filling the two gaps is worth 14.

Example 3

Input
num = "00", target = 0
Output
["0*0", "0+0", "0-0"]

The single gap can hold any of the three signs and each line is worth 0. Leaving the gap blank would make the number 00, which is not allowed.

Constraints

  • 1 <= num.length <= 10
  • num holds decimal digits only and may start with 0.
  • -2^31 <= target <= 2^31 - 1
  • Every number and every partial value stays within 10^10 in absolute size.

The values you return may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def add_operators(num: str, target: int) -> list[str]:
Java
public List<String> addOperators(String num, int target)

More on the same topics