Different Ways to Add Parentheses Problem

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.

Examples

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

Solution

Method 1 - Recursion

Here is the approach:

Expression as a Tree:
- Visualizing the expression as a tree, each operator acts as a node with its left and right operands as subtrees.
Traversal and Division:
- As we traverse the expression, whenever we encounter an operator (+, -, *), we divide the expression into the left and right parts using that operator as the pivot.
- This recursive division continues until we reach a situation where our expression is purely a number. When the expression is just a number, we can simply return that number.
Handling Multiple Evaluations:
- Since there can be multiple ways to evaluate an expression (depending on which operator we choose first), each split will generate lists of results from the left and right parts.
- For instance, an expression like 2*3-4*5 can be split multiple ways, each producing different intermediate results.
Combining Results:
- Once we have all possible results from the left and the right parts, we combine them using the current operator to produce all possible results for the current sub-expression.
- This is done by iterating through all combinations of the results from the left and right parts and applying the current operator.

For eg. for example 2, we can get:

 graph TD
     A["2*3-4*5"]
 
     subgraph "(2 * (3 - 4) * 5) = -34"
         A1("*") --> B1(2) & C1("-")
         C1 --> D1(3) & E1("*")
         E1 --> F1(4) & G1(5)
     end
 
     subgraph "((2 * 3) - (4 * 5)) = -14"
         A2("-") --> B2("*") & C2("*")
         B2 --> D2(2) & E2(3)
         C2 --> F2(4) & G2(5)
     end
     
      subgraph "(2 * ((3 - 4) * 5)) = -10"
         A4("*") --> B4("2") & C4("*")
         C4 --> D4("5") & E4("-")
         E4 --> F4(3) & G4(4)
     end

graph TD
     subgraph "(2 * 3 - 4) * 5 = 10"
         A3("*") --> B3("-") & C3(5)
         B3 --> D3("*") & E3(4)
         D3 --> F3(2) & G3(3)
     end
     
 
     subgraph "2 * (3 - 4) * 5 = -10"
         A5("*") -->  B5("*") & C5(2)
         B5 --> D5("-") & E5(5)
         D5 --> F5(3) & G5(4)
     end

Here’s a step-by-step breakdown of how to solve the problem:

Identify Operators and Numbers:
- Our input is a string containing numbers and operators +, -, *.
Recursive Function:
- Define a recursive function that computes all possible results for a given expression. For each operator in the expression, split the expression into two parts and recursively compute the results for the left and the right parts. Then combine these results using the operator.
Memoization:
- Use a dictionary to store results of computed sub-expressions to avoid redundant calculations and improve efficiency.

Code

Java

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 charAtI = expression.charAt(i);
            if (charAtI == '+' || charAtI == '-' || charAtI == '*') {
                // Split the expression into left and right parts
                String leftPart = expression.substring(0, i);
                String rightPart = expression.substring(i + 1);

                List<Integer> leftResults = diffWaysToCompute(leftPart);
                List<Integer> rightResults = diffWaysToCompute(rightPart);

                // Combine the results from left and right parts
                for (int left : leftResults) {
                    for (int right : rightResults) {
                        int result = 0;
                        switch (charAtI) {
                            case '+':
                                result = left + right;
                                break;
                            case '-':
                                result = left - right;
                                break;
                            case '*':
                                result = left * right;
                                break;
                        }
                        results.add(result);
                    }
                }
            }
        }

        // If results is empty, the current expression is a single number
        if (results.isEmpty()) {
            results.add(Integer.parseInt(expression));
        }

        memo.put(expression, results);
        return results;
    }
}

Python

class Solution:
    def __init__(self):
        self.memo = {}

    def diffWaysToCompute(self, expression: str) -> List[int]:
        if expression in self.memo:
            return self.memo[expression]

        results = []
        for i, char in enumerate(expression):
            if char in "+-*":
                # Split the expression into left and right parts
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i + 1 :])

                # Combine the results from left and right parts
                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)

        # If results is empty, the current expression is a single number
        if not results:
            results.append(int(expression))

        self.memo[expression] = results
        return results

Complexity

⏰ Time complexity: O(2^n), in the worst case for exponential splits, optimized by memoization.
🧺 Space complexity: O(2^n * r) for the memo dictionary plus O(n) recursion depth, where r is the average number of results per sub-expression.

Dry Run

We will use a recursive function that splits the expression at each operator and recursively computes the result for each side, then combines them based on the operator.

First Split at * (index 1):
- Left Part: "2"
- Right Part: "3-4*5"
- Compute results for both parts:
  - diffWaysToCompute("2"): Since “2” is a number, return [2].
  - diffWaysToCompute("3-4*5"): Recursively split and compute.
Split "3-4*5" at - (index 1):
- Left Part: "3"
- Right Part: "4*5"
- Compute results for both parts:
  - diffWaysToCompute("3"): Since “3” is a number, return [3].
  - diffWaysToCompute("4*5"): Recursively split and compute.
Split "4*5" at * (index 1):
- Left Part: "4"
- Right Part: "5"
- Compute results for both parts:
  - diffWaysToCompute("4"): Since “4” is a number, return [4].
  - diffWaysToCompute("5"): Since “5” is a number, return [5].
- Combine results based on *:
  - 4 * 5 = 20
- Result for "4*5": [20]
Combine results for "3-20" based on -:
- Compute results for left: [3]
- Compute results for right: [20]
- Combine results based on -:
  - 3 - 20 = -17
- Result for "3-4*5": [-17]
Combine results for "2*-17" based on *:
- Compute results for left: [2]
- Compute results for right: [-17]
- Combine results based on *:
  - 2 * -17 = -34
- Result for "2*3-4*5": [-34]

Next, we repeat the process for the remaining splits in the original expression "2*3-4*5":

Split at - (index 3):
- Left Part: "2*3"
- Right Part: "4*5"
- Compute results for both parts:
  - diffWaysToCompute("2*3"): Recursively split and compute.
  - diffWaysToCompute("4*5"): Previously computed as [20].
Split "2*3" at * (index 1):
- Left Part: "2"
- Right Part: "3"
- Compute results for both parts:
  - diffWaysToCompute("2"): [2]
  - diffWaysToCompute("3"): [3]
- Combine results based on *:
  - 2 * 3 = 6
- Result for "2*3": [6]
Combine results for "6-20" based on -:
- Compute results for left: [6]
- Compute results for right: [20]
- Combine results based on -:
  - 6 - 20 = -14
- Result for "2*3-4*5" (including this split): [-34, -14]

Finally, consider the last split in "2*3-4*5":

Split at * (index 5):
- Left Part: "2*3-4"
- Right Part: "5"
- Compute results for both parts:
  - diffWaysToCompute("2*3-4"): Recursively split and compute.
  - diffWaysToCompute("5"): [5]
Split "2*3-4" at * (index 1):
- Left Part: "2"
- Right Part: "3-4"
- Compute results for both parts:
  - diffWaysToCompute("2"): [2]
  - diffWaysToCompute("3-4"): Recursively split and compute.
Split "3-4" at - (index 1):
- Left Part: "3"
- Right Part: "4"
- Compute results for both parts:
  - diffWaysToCompute("3"): [3]
  - diffWaysToCompute("4"): [4]
- Combine results based on -:
  - 3 - 4 = -1
- Result for "3-4": [-1]
Combine results for "2*-1" based on *:
- Compute results for left: [2]
- Compute results for right: [-1]
- Combine results based on *:
  - 2 * -1 = -2
- Result for "2*3-4": [-2]
Combine results for (-2)*5 based on *:
- Compute results for left: [-2]
- Compute results for right: [5]
- Combine results based on *:
  - -2 * 5 = -10
- Result for "2*3-4*5": [-34, -14, -10]

Combining all the results from different splits, we include:

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

Final Result (combining all valid results from different splits): [-34, -10, -14, -10, 10]

Thus the final output of diffWaysToCompute("2*3-4*5") would be [-34, -10, -14, -10, 10].

Problem#

Examples#

Solution#

Method 1 - Recursion#

Code#

Java#

Python#

Complexity#

Dry Run#