Different Ways to Add Parentheses medium

Problem Statement

Given a string expression of numbers and operators, find all possible results from different ways of grouping the expression with parentheses. The expression will contain only numbers between 1 and 9 and the operators +, -, and *.

Example 1

Input: expression = "2-1-1"

Output: [0, 2]

Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2

Example 2

Input: expression = "23-45"

Output: [-34, -14, -10, -10, 10]

Explanation: (2*(3-(45))) = -34 ((23)-(45)) = -14 (2((3-4)5)) = -10 ((2(3-4))5) = -10 (23-(45)) = -14 ((23)-4)*5 = 10

Steps

1. Base Case: If the expression contains only one number, return a list containing that number.

2. Recursive Approach: Iterate through the expression, identifying operators. For each operator:

   • Recursively calculate all possible results for the left sub-expression.
   • Recursively calculate all possible results for the right sub-expression.
   • Combine all possible pairs of results from the left and right sub-expressions using the current operator.

3. Combine Results: Collect all results obtained from all operators in the expression.

4. Return: Return the list of all unique possible results.

Explanation

The core idea is to break down the problem into smaller subproblems using recursion. We recursively evaluate the left and right sides of each operator, then combine the results. This ensures we explore all possible parenthesizations. The use of a set ensures that we only keep unique results.

Code

def diffWaysToCompute(expression):
    """
    Calculates all possible results from different ways of grouping the expression with parentheses.

    Args:
        expression: A string representing the arithmetic expression.

    Returns:
        A list of integers representing all possible results.
    """

    if expression.isdigit():  # Base case: only a number
        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)
                    else:
                        results.append(l * r)
    return results

Complexity

• Time Complexity: O(N * 2^N), where N is the number of elements in the expression. The exponential part comes from the recursive exploration of all possible parenthesizations. The linear factor N arises from iterating through the expression.

• Space Complexity: O(N * 2^N), primarily due to the recursion depth and the storage of intermediate results. In the worst case, the number of possible results can grow exponentially with the length of the expression.