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

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.

Smallest Operator Expression Reaching a Target

Hints

1. Look at the operator that is applied last: it splits the numbers into a contiguous left block and a contiguous right block, and each block is a smaller expression of the same kind.
2. Every canonical expression over the same contiguous block has exactly the same length. What does that imply when you compare two combined strings that share a split point and an operator?
3. With at most six numbers there are only 42 * 3^5 = 10,206 expressions in total, so exploring all of them is fast enough; the real work is getting the tie-break right.

Approach

Algorithm: interval dynamic programming. For every contiguous block nums[i..j], build a table that maps each value the block can produce to the lexicographically smallest canonical string that produces it. A single number maps its value to its decimal digits. For a longer block, try every split point k (the last operator applied sits between nums[k] and nums[k+1]), every value/string pair of the left block nums[i..k], every pair of the right block nums[k+1..j], and each operator in * + -. Form "(" + left + op + right + ")", compute the value with exact 64-bit arithmetic, and keep the string if it is the first one for that value or smaller than the one stored. The answer is the table entry for target over the whole list, or "" if target is absent.

Why keeping only the smallest string per value is safe: every canonical expression over the same block has the same length (its digits plus three characters per operator). For a fixed split point and operator, two candidates "(" + L1 + op + R1 + ")" and "(" + L2 + op + R2 + ")" line up character by character. The first difference therefore falls inside L if L1 != L2, and inside R otherwise. So among all expressions with left value lv and right value rv, the smallest uses the smallest left string for lv and the smallest right string for rv. Taking the minimum over all split points, operators and value pairs yields the smallest string for every reachable value of the block.

Comparison uses plain ASCII string ordering, so ( < ) < * < + < - < digits holds automatically. Left-nested shapes win ties because an extra ( sorts before any digit.

Edge cases: a single number returns its digits when it equals target and "" otherwise. Zeros make many expressions collapse to the same value, and the tables absorb those ties. Negative values arise only through subtraction. The largest magnitude is 50^6 = 15,625,000,000, which needs 64-bit integers. It stays far below 2^53, so JavaScript numbers are exact.

• Time complexity: O(n * C(n-1) * 3^(n-1)), where C(k) is the k-th Catalan number: at most C(n-1) * 3^(n-1) = 10,206 operand combinations reach the full list when n = 6, the smaller blocks add only a constant factor, and each combination builds an O(n)-length string.
• Space complexity: O(n * C(n-1) * 3^(n-1)) for the per-block value tables, each entry holding an O(n)-length string.