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

You are given a list of integers `nums` and an integer `target`. Keep the numbers in their given order, put 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 that 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. Implement `build_target_expression(nums, target)`. ### 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 parenthesizations 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 `""`. ### Examples **Example 1** ```text Input: nums = [2, 3, 4], target = 14 Output: "(2*(3+4))" ``` 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** ```text Input: nums = [8, 3, 5, 2], target = 1 Output: "((8+3)-(5*2))" ``` 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** ```text Input: nums = [3, 3, 8], target = 3 Output: "" ``` None of the 18 canonical expressions over these three numbers evaluates to 3. ### 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 are sufficient. - For `len(nums) == 1`, the only expression is the number itself. `target` and intermediate values can exceed 2^31 - 1 (the largest reachable value is 50^6 = 15,625,000,000), so use `long` in Java and `long long` in C++ for `target` and for every computed value.