hardBacktrackingPure DSA~30 min
All Results from Differently Grouping an Expression
A formula engine evaluates an arithmetic expression of numbers and + - * operators. Different parenthesizations yield different results. Return every distinct value reachable by some valid grouping.
Problem
Given a string expression of non-negative integers and the operators '+', '-', '*', return all possible results of computing the expression under every way of grouping the numbers and operators with parentheses. Results may be returned in any order.
Input
A string expression containing digits and the operators +, -, *.
Output
A list of integers — all achievable results.
Constraints
- 1 <= expression.length <= 20
- expression contains only digits and the operators +, -, *.
- Operands fit in a 32-bit integer; results fit in a 32-bit integer.
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 produce these five values.