Scale Engineer

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
Patterns
MathRecursionDynamic ProgrammingMemoization
Data structures
String
Companies
SalesforceDeltaX

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)) = 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.

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

  1. Create a memoization map to store computed results
  2. 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
  3. Base case: if expression is a number, return the number
  4. 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.

  1. First, we parse the input string to separate numbers and operators
  2. 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
  3. 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

Solutions

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 ]; } }

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.

← Previous

Previous problem

Next →

Next problem