List All Plus/Times Expressions Reaching a Target Under Operator Precedence
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given a list of nonnegative integers and a target. Place either `+` or `*` between every pair of adjacent numbers, keeping the numbers in their original order, and return every resulting expression whose value equals the target.
This version uses standard operator precedence: all multiplications happen before any addition. For example, `2+3*4` evaluates to `2 + 12 = 14`.
This is a follow-up to a version of the problem that evaluated left to right and returned only a boolean. The interviewer asked for a new function, leaving the earlier one unchanged, that respects precedence and returns the matching expressions.
### Function Signature
```python
def find_expressions(nums: list[int], target: int) -> list[str]:
...
```
### Rules
- Exactly one operator, `+` or `*`, goes in each of the `len(nums) - 1` gaps. Numbers cannot be concatenated, reordered, skipped, or negated, and no parentheses can be added.
- Value of an expression: multiply together each maximal run of numbers joined by `*`, then add up those products.
- Write each expression as the numbers in standard decimal form with the chosen operator characters between them and no spaces. For example, `nums = [1, 2, 3]` with operators `+` and `*` is written `"1+2*3"`.
- If `nums` has one element, the only expression is that number in decimal form.
### Output
Return all matching expressions sorted in ascending lexicographic order by character code, the order Python's `sorted` produces. In this order `*` comes before `+`. Return an empty list if no expression matches. Each assignment of operators produces a different string, so the output never contains duplicates.
### Constraints
- `1 <= len(nums) <= 10`
- `0 <= nums[i] <= 30`
- `0 <= target <= 10^15`
- Intermediate and final values can exceed `2^31 - 1`, but they never exceed `30^10` (about `5.9 * 10^14`), so 64-bit integers are enough.
- There are at most `2^9 = 512` possible expressions.
### Examples
Input: `nums = [1, 2, 3], target = 7`
Output: `["1+2*3"]`
Input: `nums = [2, 2, 2], target = 6`
Output: `["2*2+2", "2+2*2", "2+2+2"]`
The only other assignment, `2*2*2`, equals `8`.
Input: `nums = [0, 5], target = 1`
Output: `[]`
Overview: Return every expression formed by placing plus or times between adjacent numbers, kept in order, that equals a target under standard operator precedence. Results are sorted lexicographically, testing enumeration of operator choices and correct handling of multiplication binding tighter than addition.
Read the full Pinterest Software Engineer interview experience this question came from
You are given a list of nonnegative integers `nums` and an integer `target`. Insert exactly one operator, either `+` or `*`, into each of the `len(nums) - 1` gaps between adjacent numbers. The numbers keep their original order: they cannot be concatenated, reordered, skipped, or negated, and no parentheses may be added.
Every expression is evaluated with standard operator precedence: all multiplications happen before any addition. Equivalently, multiply together each maximal run of numbers joined by `*`, then add up those products. For example, `2+3*4` evaluates to `2 + 12 = 14`.
Write each expression as the numbers in standard decimal form with the chosen operator characters between them and no spaces; `nums = [1, 2, 3]` with the operators `+` and `*` is written `"1+2*3"`. If `nums` has exactly one element, the only expression is that number in decimal form.
Return every expression whose value equals `target`, sorted in ascending lexicographic order by character code — the order Python's `sorted` produces — in which `*` comes before `+`, and both come before every digit. Return an empty list if no expression matches. Each assignment of operators produces a different string, so the result never contains duplicates.
Intermediate and final values can exceed `2^31 - 1` (an all-`*` expression on ten 30s is `30^10 = 590490000000000`), so use 64-bit integers: `long` in Java and `long long` in C++.
Example 1
Input: nums = [1, 2, 3], target = 7
Output: ["1+2*3"]
Explanation: the four expressions are 1*2*3 = 6, 1*2+3 = 2 + 3 = 5, 1+2*3 = 1 + 6 = 7, and 1+2+3 = 6. Only 1+2*3 equals 7.
Example 2
Input: nums = [2, 2, 2], target = 6
Output: ["2*2+2", "2+2*2", "2+2+2"]
Explanation: 2*2+2 = 4 + 2 = 6, 2+2*2 = 2 + 4 = 6, and 2+2+2 = 6 all match; the only other assignment, 2*2*2, equals 8. The three matches are returned sorted, and `*` sorts before `+`.
Constraints
- 1 <= len(nums) <= 10
- 0 <= nums[i] <= 30
- 0 <= target <= 10^15
- Intermediate and final values can exceed 2^31 - 1, but they never exceed 30^10 (about 5.9 * 10^14), so 64-bit integers are enough (long in Java, long long in C++).
- There are at most 2^9 = 512 possible expressions.
- Exactly one operator, '+' or '*', goes in each of the len(nums) - 1 gaps; numbers cannot be concatenated, reordered, skipped, or negated, and no parentheses can be added.
Examples
Input: ([7], 7)
Expected Output: ['7']
Explanation: Minimum valid size: one element has no gaps, so the only expression is the number itself, which equals the target.
Input: ([7], 8)
Expected Output: []
Explanation: Single element that does not equal the target, so no expression matches.
Hints
- Each of the len(nums) - 1 gaps independently takes one of two operators, and the constraints bound how many complete assignments there can be in total.
- Since all multiplications happen before any addition, an expression's value depends only on how its numbers split into maximal '*'-joined runs: multiply within a run, add across runs.
- The expression string and its value can be produced together while you fix operators from left to right; the required ordering applies to the collected matches at the very end, and remember that '*' sorts before '+'.