Insert +, -, * and Parentheses Between Ordered Numbers to Reach a Target

You are given a list of integers `nums` and an integer `target`. Keeping the numbers in their given order, you may insert one of the operators `+`, `-` or `*` between every pair of adjacent numbers and add parentheses in any way you like. Decide whether some resulting expression evaluates to `target`, and if it does, return such an expression. In the original interview the list always had exactly three numbers; the follow-up generalized it to `n` numbers. Your function must handle every length allowed below. ### Function Signature ```python def build_target_expression(nums: list[int], target: int) -> str: ``` ### Rules - Every number is used exactly once, in the given order. Numbers may not be reordered, joined into multi-digit numbers, or negated with a unary minus. - Exactly one operator goes between each pair of adjacent numbers. There is no division. Evaluation uses exact integer arithmetic. - Expressions are written in **canonical form**: a single number is written as its decimal digits; every binary operation is written as `(` + left operand + operator + right operand + `)` with no spaces, including the outermost operation. An expression over `k` numbers therefore has exactly `k - 1` pairs of parentheses. Different ways of parenthesizing give different strings even when they evaluate to the same value. - If at least one canonical expression evaluates to `target`, return the lexicographically smallest such string, comparing characters by their ASCII codes. In that order `(` < `)` < `*` < `+` < `-` < `0` < `1` < ... < `9`. - If no expression evaluates to `target`, return the empty string `""`. ### Constraints - `1 <= len(nums) <= 6` - `0 <= nums[i] <= 50` - `-10^11 <= target <= 10^11` - Every intermediate and final value of every expression lies within `[-10^11, 10^11]`, so 64-bit integers (and exact integer arithmetic in any language) are sufficient. - For `len(nums) == 1`, the only expression is the number itself. ### Examples **Example 1** - Input: `nums = [2, 3, 4]`, `target = 14` - Output: `"(2*(3+4))"` - Explanation: Two canonical expressions evaluate to 14: `"(2*(3+4))"` and `"(2+(3*4))"`. They first differ at the third character, where `*` comes before `+`. **Example 2** - Input: `nums = [8, 3, 5, 2]`, `target = 1` - Output: `"((8+3)-(5*2))"` - Explanation: The valid expressions are `"((8+3)-(5*2))"` and `"(8+(3-(5*2)))"`. The first is smaller because its second character is `(`, which precedes every digit. **Example 3** - Input: `nums = [3, 3, 8]`, `target = 3` - Output: `""` - Explanation: None of the 18 canonical expressions over these three numbers evaluates to 3.