# Different Ways to Add Parentheses
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/different-ways-to-add-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/different-ways-to-add-parentheses
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** String
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce), [DeltaX](https://scaleengineer.com/companies/deltax)
---
## 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 <= 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
## Recursive Approach with String Parsing
This approach involves recursively parsing the expression string and evaluating all possible combinations of parentheses by splitting the expression at each operator.
**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
**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
### Explanation
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

```java
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;
    }
}
```
### 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

## Divide and Conquer with Operator List
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.
**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
**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
### Explanation
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.

```java
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;
        }
    }
}
```
### Algorithm
1. Parse expression into separate lists of numbers and operators
2. 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
3. Store intermediate results in memoization map

# Solutions
### CSharp

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

### Java

```java
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 ; } }
```

### Python

```python
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 )]

```

### CPP

```cpp
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;
};

```