Different Ways to Add Parentheses solution and explanation
Google
9 more videos on this problem
leetcode 241 Different Ways to Add ParenthesesCodebix · 12:33 · 27K views
Different Ways to Add Parentheses - Leetcode 241 - PythonNeetCodeIO · 15:14 · 21K views
Different Ways to Add Parentheses | Simple Story To Code | Leetcode 241 | codestorywithMIKcodestorywithMIK · 21:45 · 18K views
[Java] Leetcode 241. Different Ways to Add Parentheses [Backtracking #13]Eric Programming · 18:01 · 6K views
Different Ways to Add Parentheses(Leetcode: 241)CodeCourses · 7:12 · 5K views
241. Different Ways to Add Parentheses | DP | recursion | Leetcode Daily Challenge | DSA | JavaShashCode · 23:01 · 3K views
Different Ways to Add Parentheses | Leetcode 241Techdose · 22:25 · 3K views
241. Different Ways to Add Parentheses (Leetcode Medium)Programming Live with Larry · 14:06 · 2K views
LeetCode 241. [Medium] Different Ways to Add ParenthesesFrancesco Manicardi · 3:43 · 1K views
241. Different Ways to Add Parentheses (Leetcode)hakunamatasq · 10:54 · 687 views
The problem
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 = "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 <= 20expressionconsists 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.
def diffWaysToCompute(expression):
if expression.isdigit():
return [int(expression)]
results = []
for i, char in enumerate(expression):
if char in "+-*":
left = diffWaysToCompute(expression[:i])
right = diffWaysToCompute(expression[i+1:])
for l in left:
for r in right:
if char == '+':
results.append(l + r)
elif char == '-':
results.append(l - r)
elif char == '*':
results.append(l * r)
return results
# Example Usage
print(diffWaysToCompute("2*3-4*5"))import java.util.*;
public class Solution {
public List<Integer> diffWaysToCompute(String expression) {
List<Integer> results = new ArrayList<>();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(expression.substring(0, i));
List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case '+': results.add(l + r); break;
case '-': results.add(l - r); break;
case '*': results.add(l * r); break;
}
}
}
}
}
if (results.isEmpty()) {
results.add(Integer.parseInt(expression));
}
return results;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.diffWaysToCompute("2*3-4*5"));
}
}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.
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.
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.
def diffWaysToCompute(expression, memo={}):
if expression in memo:
return memo[expression]
if expression.isdigit():
return [int(expression)]
results = []
for i, char in enumerate(expression):
if char in "+-*":
left = diffWaysToCompute(expression[:i], memo)
right = diffWaysToCompute(expression[i+1:], memo)
for l in left:
for r in right:
if char == '+':
results.append(l + r)
elif char == '-':
results.append(l - r)
elif char == '*':
results.append(l * r)
memo[expression] = results
return results
# Example Usage
print(diffWaysToCompute("2*3-4*5"))import java.util.*;
public class Solution {
private Map<String, List<Integer>> memo = new HashMap<>();
public List<Integer> diffWaysToCompute(String expression) {
if (memo.containsKey(expression)) {
return memo.get(expression);
}
List<Integer> results = new ArrayList<>();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(expression.substring(0, i));
List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case '+': results.add(l + r); break;
case '-': results.add(l - r); break;
case '*': results.add(l * r); break;
}
}
}
}
}
if (results.isEmpty()) {
results.add(Integer.parseInt(expression));
}
memo.put(expression, results);
return results;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.diffWaysToCompute("2*3-4*5"));
}
}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.
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.
Approach 3: Default Approach
class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
return dfs(expression);
}
vector<int> dfs(string exp) {
if (memo.count(exp)) return memo[exp];
if (exp.size() < 3) return {stoi(exp)};
vector<int> ans;
int n = exp.size();
for (int i = 0; i < n; ++i) {
char c = exp[i];
if (c == '-' || c == '+' || c == '*') {
vector<int> left = dfs(exp.substr(0, i));
vector<int> right = dfs(exp.substr(i + 1, n - i - 1));
for (int& a : left) {
for (int& b : right) {
if (c == '-')
ans.push_back(a - b);
else if (c == '+')
ans.push_back(a + b);
else
ans.push_back(a * b);
}
}
}
}
memo[exp] = ans;
return ans;
}
private:
unordered_map<string, vector<int>> memo;
};using System.Collections.Generic;
public class Solution {
public IList<int> DiffWaysToCompute(string input) {
var values = new List<int>();
var operators = new List<char>();
var sum = 0;
foreach (var ch in input)
{
if (ch == '+' || ch == '-' || ch == '*')
{
values.Add(sum);
operators.Add(ch);
sum = 0;
}
else
{
sum = sum * 10 + ch - '0';
}
}
values.Add(sum);
var f = new List<int>[values.Count, values.Count];
for (var i = 0; i < values.Count; ++i)
{
f[i, i] = new List<int> { values[i] };
}
for (var diff = 1; diff < values.Count; ++diff)
{
for (var left = 0; left + diff < values.Count; ++left)
{
var right = left + diff;
f[left, right] = new List<int>();
for (var i = left; i < right; ++i)
{
foreach (var leftValue in f[left, i])
{
foreach (var rightValue in f[i + 1, right])
{
switch (operators[i])
{
case '+':
f[left, right].Add(leftValue + rightValue);
break;
case '-':
f[left, right].Add(leftValue - rightValue);
break;
case '*':
f[left, right].Add(leftValue * rightValue);
break;
}
}
}
}
}
}
return f[0, values.Count - 1];
}
}var memo = map[string][]int{}
func diffWaysToCompute(expression string) []int {
return dfs(expression)
}
func dfs(exp string) []int {
if v, ok := memo[exp]; ok {
return v
}
if len(exp) < 3 {
v, _ := strconv.Atoi(exp)
return []int{v}
}
ans := []int{}
for i, c := range exp {
if c == '-' || c == '+' || c == '*' {
left, right := dfs(exp[:i]), dfs(exp[i+1:])
for _, a := range left {
for _, b := range right {
if c == '-' {
ans = append(ans, a-b)
} else if c == '+' {
ans = append(ans, a+b)
} else {
ans = append(ans, a*b)
}
}
}
}
}
memo[exp] = ans
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Divide and Conquer with Recursion | Time Complexity: O(2^n) - In the worst case, the algorithm evaluates every partition. |
| Dynamic Programming with Memoization | Time Complexity: O(n^3) - n^2 subproblems with evaluation cost per subproblem. |
| Default Approach | – |
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 |
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.