List All Plus/Times Expressions Reaching a Target Under Operator Precedence

Problem Statement

Given a list of non-negative integers nums and an integer target, insert either an addition operator (+) or a multiplication operator (*) between every adjacent pair of numbers in nums such that the resulting arithmetic expression evaluates to target.

Multiplication has higher precedence than addition (standard arithmetic rules apply). You must preserve the original order of numbers in nums, and exactly one operator must be placed between each adjacent pair.

Return a list of all valid expressions as strings, sorted in lexicographical (ASCII) order. If no valid expression exists, return an empty list.

Function Interface

def find_expressions(nums: list[int], target: int) -> list[str]:
    """
    Returns all expressions formed by inserting '+' or '*' between
    adjacent elements of nums that evaluate to target.
    """
    pass

Examples

Example 1

Input: nums = [1, 2, 3, 4], target = 11
Output: ["1+2*3+4"]
Explanation:
Evaluating 1 + 2 * 3 + 4 under standard precedence:
2 * 3 = 6
1 + 6 + 4 = 11
None of the other 7 operator combinations evaluate to 11.

Example 2

Input: nums = [2, 3, 2], target = 8
Output: ["2+3*2", "2*3+2"]
Explanation:
"2+3*2" evaluates to 2 + 6 = 8.
"2*3+2" evaluates to 6 + 2 = 8.
In ASCII order, '*' (ASCII 42) comes before '+' (ASCII 43), so "2*3+2" appears before "2+3*2" if compared at index 1.

Constraints

• 1 <= len(nums) <= 16
• 0 <= nums[i] <= 100
• -2^31 <= target <= 2^31 - 1

Edge Cases

• A single number (len(nums) == 1): No operators can be inserted. Return [str(nums[0])] if nums[0] == target, else [].
• Presence of 0 in nums: Multiplications with zero should be handled correctly without affecting earlier summed terms.
• Expressions where all combinations evaluate to values strictly greater or strictly less than target.