hardDynamic Programming 2DPure DSA~40 min
All Results From Different Operator Groupings
Given an arithmetic expression of numbers and +, -, * operators, compute every possible result obtainable by inserting parentheses in different ways.
Problem
Given a string expression of numbers and operators (+, -, *), return all possible results from grouping the numbers and operators differently. The results may be returned in any order.
Input
An expression string of integers and the operators +, -, *.
Output
A list of all distinct grouping results (duplicates allowed).
Constraints
- 1 <= expression.length <= 20
- Operands are small non-negative integers.
- The number of results stays bounded (Catalan-scale).
Examples
Example 1
Input
expression = "2-1-1"
Output
[0,2]
(2-1)-1 = 0 and 2-(1-1) = 2.
Example 2
Input
expression = "2*3-4*5"
Output
[-34,-14,-10,-10,10]
Different groupings yield these five values.