Different Ways to Add Parentheses
Medium · Backtracking · Math · String · Dynamic Programming · Recursion · Memoization
Problem
You are given a string expression made of non-negative integers and the binary operators +, - and *. Every way of fully parenthesizing the expression fixes an order in which the operators are applied.
Return the result of every possible grouping, in any order. If two different groupings give the same value, list it once for each grouping. The answers fit in a 32-bit integer, and there are at most 10^4 of them.
Examples
Input: expression = "4*2+1" Output: [12,9]
4*(2+1) gives 12 and (4*2)+1 gives 9.
Input: expression = "5-2-1" Output: [4,2]
5-(2-1) gives 4 and (5-2)-1 gives 2.
Input: expression = "2*3-4*5" Output: [-34,-14,-10,-10,10]
Five groupings: 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. The value -10 appears twice because two groupings give it.
Constraints
- 1 <= len(expression) <= 20
- expression consists of digits and the operators +, - and *
- Every integer in expression is in the range [0, 99]
- Integers have no leading sign
Approaches
- Baseline: plain recursion on substrings — time exponential: sub-expressions are recomputed for every split that contains them, space O(n) recursion depth plus the output
Follow-up
The number of groupings of m + 1 numbers is the Catalan number C(m): 1, 1, 2, 5, 14, 42, ... so the output itself grows exponentially; caching only stops the same ranges from being recomputed. If you need just the largest result, keep only the minimum and maximum per range (a product of two negatives can be the new maximum), which makes it O(m³).
Related problems
Start free on Cariara · Coding problems · System design studio
