Different Ways to Add Parentheses

Different Ways to Add Parentheses is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Catalan Numbers subpattern.

Problem statement

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 104.

Example 1:

Input: expression = "2-1-1" Output: [0,2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2

Example 2:

Input: expression = "23-45" Output: [-34,-14,-10,-10,10] Explanation: (2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10

Constraints:

- 1 <= expression.length <= 20

- expression consists of digits and the operator '+', '-', and ''.

- All the integer values in the input expression are in the range [0, 99].

- The integer values in the input expression do not have a leading '-' or '+' denoting the sign.

Topics and companies

Topics: Math, String, Dynamic Programming, Recursion, Memoization.

Reported in interviews at Microsoft, Flipkart.

How to practise Different Ways to Add Parentheses on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N * 2^N), where N is the length of the expression. For each operator, we split and recursively compute all combinations, and the number of ways to parenthesize grows exponentially (Catalan number). time and O(N^2 * K), where N is the length of the expression and K is the average number of results per substring (due to memoization of all subproblems). space.

Open Different Ways to Add Parentheses in the code editor, or read the Different Ways to Add Parentheses editorial for a worked solution with its approach and complexity analysis.

Where Different Ways to Add Parentheses sits in the DSA pattern sheet

Problems related to Different Ways to Add Parentheses

Other problems that use the same Catalan Numbers and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.