Different Ways to Add Parentheses - Solution & Explanation

Q: Is Different Ways to Add Parentheses easy or hard?

The problem is rated Medium on LeetCode. The recursion idea is straightforward, but recognizing overlapping subproblems and adding memoization makes the solution more efficient and interview-ready.

Q: Different Ways to Add Parentheses Python/Java solution

In Python or Java, iterate through the expression and split whenever you encounter an operator. Recursively compute results for the left and right substrings, combine them with the operator, and store results in a memoization map keyed by the substring.

Q: How to solve Different Ways to Add Parentheses in O(n)?

An O(n) solution does not exist because the number of valid parenthesizations grows exponentially with the number of operators. Even the optimal solution must generate every possible result. The most efficient practical solution uses recursion with memoization and runs in about O(n * 2^n) time.

Q: What is the best approach for Different Ways to Add Parentheses?

The best approach uses divide and conquer with memoization. Split the expression at every operator, recursively compute results for the left and right parts, then combine them. Caching results for each substring avoids recomputation and significantly improves performance compared to pure recursion.

Q: Is Different Ways to Add Parentheses asked at Google/Amazon/Meta?

Expression evaluation and divide-and-conquer problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Interviewers use it to test recursion design, handling overlapping subproblems, and applying memoization or dynamic programming.

Q: What data structure is used in Different Ways to Add Parentheses?

The main data structure is a hash map used for memoization, mapping each substring to the list of results it can produce. Lists or arrays store intermediate results, while recursion handles splitting the expression around operators.

Q: What is the time complexity of Different Ways to Add Parentheses?

The time complexity is approximately O(n * 2^n). The algorithm must explore all possible parenthesizations of the expression, which grows exponentially. Memoization prevents repeated computation of the same substrings but the total number of possible result combinations still drives the complexity.

MediumMath String Dynamic Programming Recursion9 min readAsked at: Amazon, Microsoft, Deutsche Bank +3

Practice this problem

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 10⁴.

Example 1:

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

Example 2:

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-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.

Approach Overview

Problem Overview: You receive a string expression containing numbers and the operators +, -, and *. The task is to compute every possible result produced by inserting parentheses in different valid ways. Each parenthesization changes the evaluation order, so the output is a list of all possible computed values.

Approach 1: Divide and Conquer with Recursion (Time: O(n * 2^n), Space: O(n * 2^n))

Treat every operator as a potential split point. When you encounter an operator while iterating through the expression, divide the string into a left and right subexpression. Recursively compute all possible results for the left side and all results for the right side. Then combine every pair of results using the current operator. For example, if the left side returns [2,3] and the right side returns [4,5], compute all combinations like 2+4, 2+5, 3+4, 3+5. The recursion continues until a substring contains only digits, which becomes the base case. This approach relies heavily on recursion and a classic divide-and-conquer pattern: break the expression at operators, solve subproblems, then merge their results. The downside is repeated work because the same substrings get recomputed many times.

Approach 2: Dynamic Programming with Memoization (Time: O(n * 2^n), Space: O(n * 2^n))

The recursive strategy becomes much faster when you cache results for each substring. Use a dictionary or hash map where the key is the substring and the value is the list of computed results. Before solving a subexpression, check the cache. If results already exist, reuse them immediately instead of recomputing the recursion tree. This drastically reduces repeated work, especially for overlapping subexpressions like "2*3" appearing in multiple splits. The algorithm still explores all valid parenthesizations, but memoization ensures each substring is solved only once. Conceptually this combines dynamic programming with memoization, while still using recursion to generate partitions of the expression. It performs well because most expressions contain many repeated substructures.

Recommended for interviews: Start by explaining the divide-and-conquer recursion. It clearly demonstrates the core insight: every operator splits the problem into two independent subexpressions. After that, mention the optimization with memoization. Interviewers usually expect the memoized version because it shows awareness of overlapping subproblems and dynamic programming techniques while preserving the clean recursive structure.

Approach 1: Divide and Conquer with Recursion

The problem can be approached by using recursion to divide the expression into sub-expressions at each operator, evaluating each possible combination. For each operator, compute the left and right sub-expressions separately, then combine their results based on the operator. This allows us to explore all possible ways to parenthesize the expression and evaluate it.

This Python solution uses recursion to break down the expression into all possible pairs of sub-expressions partitioned by operators. It recursively computes the result for each pair and combines them according to the operator. The function checks if the expression is a single number and returns it as a list; otherwise, it iterates through the expression characters, recursively calls itself for partitions, and calculates possible results.

Code

Python Java

Python

Java

Complexity

Time Complexity: O(2^n) - In the worst case, the algorithm evaluates every partition.
Space Complexity: O(2^n) - due to the recursion depth and storage of intermediate results.

Try this approach in the editor →

Approach 2: Dynamic Programming with Memoization

To optimize the recursive approach, we can use memoization to cache the results of subproblems. This avoids redundant evaluations of the same sub-expressions, thereby optimizing the time complexity. We store results of sub-expressions in a hash map and reuse them when the same sub-expression is encountered again.

This Python solution is a memoized version of the recursive approach. It maintains a dictionary to store results of computed sub-expressions. Before calculating a sub-expression, it checks if the result is already available. If so, it reuses the result from the dictionary; otherwise, it calculates and stores it. This method significantly reduces redundant calculations.

Code

Python Java

Python

Java

Complexity

Time Complexity: O(n^3) - n^2 subproblems with evaluation cost per subproblem.
Space Complexity: O(n^2) - for storing results of subproblems in a memoization table.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go C#

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Divide and Conquer with Recursion	Time Complexity: O(2^n) - In the worst case, the algorithm evaluates every partition. Space Complexity: O(2^n) - due to the recursion depth and storage of intermediate results.
Dynamic Programming with Memoization	Time Complexity: O(n^3) - n^2 subproblems with evaluation cost per subproblem. Space Complexity: O(n^2) - for storing results of subproblems in a memoization table.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Divide and Conquer Recursion	O(n * 2^n)	O(n * 2^n)	Good for understanding the core idea of splitting expressions at operators
Dynamic Programming with Memoization	O(n * 2^n)	O(n * 2^n)	Preferred solution when avoiding repeated computation of the same substrings

Video Solution

leetcode 241 Different Ways to Add Parentheses • Codebix • 27,180 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Different Ways to Add Parentheses easy or hard?

The problem is rated Medium on LeetCode. The recursion idea is straightforward, but recognizing overlapping subproblems and adding memoization makes the solution more efficient and interview-ready.

Different Ways to Add Parentheses Python/Java solution

In Python or Java, iterate through the expression and split whenever you encounter an operator. Recursively compute results for the left and right substrings, combine them with the operator, and store results in a memoization map keyed by the substring.

How to solve Different Ways to Add Parentheses in O(n)?

An O(n) solution does not exist because the number of valid parenthesizations grows exponentially with the number of operators. Even the optimal solution must generate every possible result. The most efficient practical solution uses recursion with memoization and runs in about O(n * 2^n) time.

What is the best approach for Different Ways to Add Parentheses?

The best approach uses divide and conquer with memoization. Split the expression at every operator, recursively compute results for the left and right parts, then combine them. Caching results for each substring avoids recomputation and significantly improves performance compared to pure recursion.

Is Different Ways to Add Parentheses asked at Google/Amazon/Meta?

Expression evaluation and divide-and-conquer problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Interviewers use it to test recursion design, handling overlapping subproblems, and applying memoization or dynamic programming.

What data structure is used in Different Ways to Add Parentheses?

The main data structure is a hash map used for memoization, mapping each substring to the list of results it can produce. Lists or arrays store intermediate results, while recursion handles splitting the expression around operators.

What is the time complexity of Different Ways to Add Parentheses?

The time complexity is approximately O(n * 2^n). The algorithm must explore all possible parenthesizations of the expression, which grows exponentially. Memoization prevents repeated computation of the same substrings but the total number of possible result combinations still drives the complexity.

Ready to solve this problem?

Practice Different Ways to Add Parentheses with our built-in code editor and test cases.

Practice on FleetCode

Basic Calculator

Expression Add Operators

Problem Info

DifficultyMedium

Acceptance73.1%

Approaches3

Reading time9 min

Asked at

Amazon Microsoft Deutsche Bank Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Divide and Conquer with Recursion

Code

Complexity

Approach 2: Dynamic Programming with Memoization

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents