Insert Operators to Reach a Target

Problem Statement

Given a string of digits num and an integer target, return all possible mathematical expressions formed by inserting the binary operators +, -, and * between digits of num such that the expression evaluates to target.

The returned list must be sorted in lexicographical (ASCII) order.

Rules

• Operators allowed: +, -, *.
• You may also choose not to insert an operator between adjacent digits, concatenating them into a multi-digit number.
• Multi-digit numbers cannot have leading zeros (for example, "05" is invalid, but "0" alone or "50" is valid).
• Standard operator precedence applies: multiplication (*) takes precedence over addition (+) and subtraction (-).
• You cannot change the relative order of the digits in num.

Function Signature

def add_operators(num: str, target: int) -> list[str]:
    pass

Constraints

• 1 <= len(num) <= 10
• num consists solely of digits '0' through '9'.
• -2^31 <= target <= 2^31 - 1

Examples

Example 1

Input: num = "123", target = 6
Output: ["1*2*3", "1+2+3"]
Explanation: Both 1*2*3 = 6 and 1+2+3 = 6. In ASCII order, "1*2*3" comes before "1+2+3".

Example 2

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
Explanation: Both 2*3+2 = 8 and 2+3*2 = 8.

Example 3

Input: num = "105", target = 5
Output: ["1*0+5", "10-5"]
Explanation: "10-5" is valid because "10" has no leading zero. "1-05" would be invalid.

Edge Cases

• Single-digit num where int(num) == target should return [num].
• Numbers that start with '0' must not be extended into multi-digit numbers (e.g., if you pick '0', you cannot concatenate further to make '05').
• If no expression can evaluate to target, return an empty list [].