221. Different Ways to Add Parentheses
You get a string expression: non-negative integers joined by the binary operators +, -, and *, with no parentheses and no spaces (for example "2*3-4*5").
Every way of fully parenthesizing the expression pins down an evaluation order and yields one number. Compute the value of every possible parenthesization and return the results sorted in non-decreasing order, keeping duplicates — if two different groupings happen to produce the same number, it appears twice.
For "2-1-1" the two groupings are (2-1)-1 = 0 and 2-(1-1) = 2, so the answer is [0, 2]. Think about what choosing "the operator applied last" does to the two sides of the expression.
Example 1:
Input: expression = "2-1-1"
Output: [0, 2]
Explanation: (2-1)-1 = 0 and 2-(1-1) = 2. Sorted: 0 2.
Example 2:
Input: expression = "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: The five groupings give 2*(3-(4*5)) = -34, (2*3)-(4*5) = -14, 2*((3-4)*5) = -10, ((2*3)-4)*5 = 10 and (2*(3-4))*5 = -10 — note the duplicate -10 from two different groupings.
Constraints:
- 1 ≤ expression.length ≤ 20
- expression consists of digits and the operators '+', '-' and '*'.
- Every number in the expression is an integer in the range [0, 99].
- The expression is well-formed: it starts and ends with a number, and each operator sits between two numbers.
Hints:
Pick any operator and declare it the one evaluated **last**. Everything to its left must collapse to a single value first, and likewise everything to its right — two smaller copies of the same problem.
Recurse: for each operator at position i, combine every value the left substring can produce with every value the right substring can produce. A substring with no operators is just a number — that's the base case. Sort the collected values before returning.
The same substring gets re-solved many times across different splits. Memoize results per substring and the recursion tree collapses into a table.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: expression = "2-1-1"
Expected output: [0, 2]