Different Ways to Add Parentheses
Med#0229Time: O(n * 2^n) where n is the length of the expression. Each position can be split in two ways, and we need to process each split.Space: O(n * 2^n) for storing all possible results in the memoization map2 companies
Prompt
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)) = 2Example 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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves recursively parsing the expression string and evaluating all possible combinations of parentheses by splitting the expression at each operator.
Algorithm
- Create a memoization map to store computed results
- For each character in expression:
- If character is an operator, split expression at that point
- Recursively compute results for left and right parts
- Combine results using the operator
- Base case: if expression is a number, return the number
- Store results in memo map and return
Walkthrough
The idea is to recursively split the expression at each operator and compute all possible results for the left and right parts. Then combine these results using the operator at the split point.
- First, we parse the input string to separate numbers and operators
- For each operator position, we:
- Split the expression into left and right parts
- Recursively calculate all possible results for left and right parts
- Combine the results using the current operator
- Use memoization to store intermediate results
class Solution { 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<>(); // Base case: if expression is just a number if (!expression.contains("*") && !expression.contains("+") && !expression.contains("-")) { results.add(Integer.parseInt(expression)); return results; } 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) { if (c == '*') results.add(l * r); else if (c == '+') results.add(l + r); else results.add(l - r); } } } } memo.put(expression, results); return results; }}Complexity
Time
O(n * 2^n) where n is the length of the expression. Each position can be split in two ways, and we need to process each split.
Space
O(n * 2^n) for storing all possible results in the memoization map
Trade-offs
Pros
Simple and intuitive implementation
Handles all possible combinations of parentheses
Memoization helps avoid redundant calculations
Cons
High time and space complexity
String parsing overhead
May not be efficient for very long expressions
This approach improves upon the basic recursive solution by first separating the expression into lists of numbers and operators, eliminating the need for repeated string parsing.
Algorithm
- Parse expression into separate lists of numbers and operators
- Use divide and conquer approach with memoization:
- Split the expression at each operator
- Recursively compute results for left and right parts
- Combine results using the operator
- Store intermediate results in memoization map
Walkthrough
Instead of working directly with the string, we first parse it into separate lists of numbers and operators. This eliminates repeated string parsing during recursion.
class Solution { Map<String, List<Integer>> memo = new HashMap<>(); public List<Integer> diffWaysToCompute(String expression) { List<Integer> numbers = new ArrayList<>(); List<Character> operators = new ArrayList<>(); // Parse expression into numbers and operators int num = 0; for (char c : expression.toCharArray()) { if (Character.isDigit(c)) { num = num * 10 + (c - '0'); } else { numbers.add(num); operators.add(c); num = 0; } } numbers.add(num); return computeResults(numbers, operators, 0, numbers.size() - 1); } private List<Integer> computeResults(List<Integer> numbers, List<Character> operators, int start, int end) { String key = start + "-" + end; if (memo.containsKey(key)) return memo.get(key); List<Integer> results = new ArrayList<>(); if (start == end) { results.add(numbers.get(start)); return results; } for (int i = start; i < end; i++) { List<Integer> leftResults = computeResults(numbers, operators, start, i); List<Integer> rightResults = computeResults(numbers, operators, i + 1, end); char op = operators.get(i); for (int left : leftResults) { for (int right : rightResults) { results.add(calculate(left, right, op)); } } } memo.put(key, results); return results; } private int calculate(int a, int b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; default: return a * b; } }}Complexity
Time
O(n * 2^n) where n is the length of the expression, but with better constant factors than the first approach
Space
O(n * 2^n) for storing results, but with lower memory overhead than string-based approach
Trade-offs
Pros
More efficient than string parsing approach
Better memory usage due to working with primitive types
Cleaner and more maintainable code structure
Faster execution due to elimination of string operations
Cons
Still has exponential complexity
Initial parsing step adds slight overhead
May not handle very large numbers efficiently
Solutions
Solution
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 ]; } }import java.util.ArrayList ; import java.util.List ; public class Different_Ways_to_Add_Parentheses { public class Solution { public List < Integer > diffWaysToCompute ( String input ) { List < Integer > result = new ArrayList <>(); if ( input == null || input . length () == 0 ) { return result ; } for ( int i = 0 ; i < input . length (); i ++) { char c = input . charAt ( i ); if (! isOperator ( c )) { continue ; } List < Integer > left = diffWaysToCompute ( input . substring ( 0 , i )); List < Integer > right = diffWaysToCompute ( input . substring ( i + 1 )); for ( int num1 : left ) { for ( int num2 : right ) { int val = calculate ( num1 , num2 , c ); result . add ( val ); } } } // only contains one number if ( result . isEmpty ()) { result . add ( Integer . parseInt ( input )); } return result ; } private int calculate ( int num1 , int num2 , char operator ) { int result = 0 ; switch ( operator ) { case '+' : result = num1 + num2 ; break ; case '-' : result = num1 - num2 ; break ; case '*' : result = num1 * num2 ; break ; } return result ; } private boolean isOperator ( char operator ) { return ( operator == '+' ) || ( operator == '-' ) || ( operator == '*' ); } } } ############ class Solution { private static Map < String , List < Integer >> memo = new HashMap <>(); public List < Integer > diffWaysToCompute ( String expression ) { return dfs ( expression ); } private List < Integer > dfs ( String exp ) { if ( memo . containsKey ( exp )) { return memo . get ( exp ); } List < Integer > ans = new ArrayList <>(); if ( exp . length () < 3 ) { ans . add ( Integer . parseInt ( exp )); return ans ; } for ( int i = 0 ; i < exp . length (); ++ i ) { char c = exp . charAt ( i ); if ( c == '-' || c == '+' || c == '*' ) { List < Integer > left = dfs ( exp . substring ( 0 , i )); List < Integer > right = dfs ( exp . substring ( i + 1 )); for ( int a : left ) { for ( int b : right ) { if ( c == '-' ) { ans . add ( a - b ); } else if ( c == '+' ) { ans . add ( a + b ); } else { ans . add ( a * b ); } } } } } memo . put ( exp , ans ); return ans ; } }class Solution: def diffWaysToCompute(self, expression: str) -> List[int]: @ cache # note def dfs ( exp ): if exp . isdigit (): return [ int ( exp )] # return list ans = [] for i , c in enumerate ( exp ): if c in '-+*' : left , right = dfs ( exp [: i ]), dfs ( exp [ i + 1 :]) for a in left : for b in right : if c == '-' : ans . append ( a - b ) elif c == '+' : ans . append ( a + b ) else : ans . append ( a * b ) return ans return dfs ( expression ) ############ ''' >>> from operator import * >>> add(1,2) 3 >>> sub(1,2) -1 >>> mul(1,2) 2 >>> div(1,2) 0 ### append() vs extend() >>> x = [1, 2, 3] >>> x.append([4, 5]) >>> print(x) [1, 2, 3, [4, 5]] >>> x = [1, 2, 3] >>> x.extend([4, 5]) >>> print(x) [1, 2, 3, 4, 5] https://stackoverflow.com/questions/252703/what-is-the-difference-between-pythons-list-methods-append-and-extend ''' from operator import * class Solution ( object ): def diffWaysToCompute ( self , input ): """ :type input: str :rtype: List[int] """ ops = { "+" : add , "-" : sub , "*" : mul , "/" : div } ans = [] for i , c in enumerate ( input ): if c in ops : left = self . diffWaysToCompute ( input [: i ]) right = self . diffWaysToCompute ( input [ i + 1 :]) ans . extend ([ ops [ c ]( a , b ) for a in left for b in right ]) return ans if ans else [ int ( input )]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;};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.