LeetCode 241: Different Ways to Add Parentheses

Problem Restatement

We are given a string expression containing:

• Non-negative integers
• Operators:
  • +
  • -
  • *

We need to compute all possible results from adding parentheses in every valid way.

The answer may contain duplicate values if different parenthesizations produce the same result.

LeetCode examples include:

Input:  expression = "2-1-1"
Output: [0,2]

and:

Input:  expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]

The expression length is at most 20. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def diffWaysToCompute(self, expression: str) -> list[int]:
        ...

Examples

Example 1:

Input:  "2-1-1"
Output: [0,2]

Two valid parenthesizations exist.

First way

(2 - 1) - 1

Result:

0

Second way

2 - (1 - 1)

Result:

2

So the answer is:

[0, 2]

Example 2:

Input:  "2*3-4*5"

Different parenthesizations produce:

-34
-14
-10
-10
10

Duplicates are kept.

First Thought: Try Every Parenthesization

The expression can split at every operator.

For:

2*3-4*5

possible top-level splits are:

2 | * | 3-4*5
2*3 | - | 4*5
2*3-4 | * | 5

Each split creates:

• A left subexpression
• A right subexpression

If we know all possible results for both sides, we can combine them using the operator.

This naturally suggests recursion.

Key Insight

Every operator can become the final operation of some parenthesization.

For example:

2*3-4*5

If we choose - as the final operation:

(2*3) - (4*5)

Then:

• The left side itself may have multiple results.
• The right side itself may have multiple results.

So the problem breaks into smaller versions of the same problem.

This is classic divide and conquer recursion.

Recursive Structure

Define:

solve(expr)

to return:

all possible results of expr

Then for every operator:

1. Solve the left part recursively.
2. Solve the right part recursively.
3. Combine every left result with every right result.

Base Case

If the expression contains no operator, then it is just a number.

Example:

"123"

Result:

[123]

This becomes the recursion base case.

Combining Results

Suppose:

left_results  = [2, 3]
right_results = [4, 5]
operator = *

Then all combinations are:

2 * 4 = 8
2 * 5 = 10
3 * 4 = 12
3 * 5 = 15

So the combined results are:

[8, 10, 12, 15]

Algorithm

For an expression:

1. Initialize an empty result list.
2. Scan the expression character by character.
3. Whenever we see an operator:
   • Split the expression into left and right parts.
   • Recursively compute all results for both parts.
   • Combine every left result with every right result.
4. If no operator exists:
   • Convert the expression to an integer.
   • Return it as a single-element list.

Walkthrough

Use:

"2-1-1"

Possible splits:

Split at first -

2 | - | 1-1

Left results:

[2]

Right results:

[0]

Combine:

2 - 0 = 2

Split at second -

2-1 | - | 1

Left results:

[1]

Right results:

[1]

Combine:

1 - 1 = 0

Final answer:

[2, 0]

Order does not matter.

Correctness

We prove the algorithm returns exactly all possible results.

Every valid parenthesization has some final operation applied last. That final operation corresponds to one operator position in the expression.

When the algorithm splits at an operator, it considers all possible results of the left subexpression and all possible results of the right subexpression recursively.

By the recursive definition, those recursive calls already contain every valid result for the two subexpressions.

The algorithm then combines every left result with every right result using the current operator. Therefore, it generates every valid result whose final operation is that operator.

Since the algorithm repeats this for every operator position, it generates results for every possible parenthesization.

The base case handles pure numbers correctly by returning the numeric value itself.

Therefore, the algorithm returns exactly all valid computation results.

Complexity

The number of possible parenthesizations grows exponentially.

The exact count is related to Catalan numbers.

Because many subexpressions repeat, memoization can significantly improve performance.

Implementation Without Memoization

class Solution:
    def diffWaysToCompute(self, expression: str) -> list[int]:
        results = []

        for i, ch in enumerate(expression):
            if ch in "+-*":
                left_results = self.diffWaysToCompute(expression[:i])
                right_results = self.diffWaysToCompute(expression[i + 1:])

                for left in left_results:
                    for right in right_results:
                        if ch == "+":
                            results.append(left + right)

                        elif ch == "-":
                            results.append(left - right)

                        else:
                            results.append(left * right)

        if not results:
            results.append(int(expression))

        return results

Code Explanation

We scan the expression:

for i, ch in enumerate(expression):

Whenever we find an operator:

if ch in "+-*":

we split the expression:

expression[:i]
expression[i + 1:]

Then recursively compute all possible results for both sides:

left_results = self.diffWaysToCompute(expression[:i])
right_results = self.diffWaysToCompute(expression[i + 1:])

Now combine every pair:

for left in left_results:
    for right in right_results:

Apply the operator:

if ch == "+":
    results.append(left + right)

and similarly for - and *.

If no operator was found:

if not results:

then the expression is just a number:

results.append(int(expression))

Memoization Optimization

Many subexpressions repeat.

For example:

2*3-4*5

may repeatedly solve:

"4*5"

Memoization stores already-computed results.

Optimized Implementation

from functools import cache

class Solution:
    @cache
    def diffWaysToCompute(self, expression: str) -> list[int]:
        results = []

        for i, ch in enumerate(expression):
            if ch in "+-*":
                left_results = self.diffWaysToCompute(expression[:i])
                right_results = self.diffWaysToCompute(expression[i + 1:])

                for left in left_results:
                    for right in right_results:
                        if ch == "+":
                            results.append(left + right)

                        elif ch == "-":
                            results.append(left - right)

                        else:
                            results.append(left * right)

        if not results:
            results.append(int(expression))

        return results

The @cache decorator remembers previously computed subexpressions automatically.

Testing

def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(s.diffWaysToCompute("2-1-1")) == [0, 2]

    assert normalize(s.diffWaysToCompute("2*3-4*5")) == [
        -34,
        -14,
        -10,
        -10,
        10,
    ]

    assert normalize(s.diffWaysToCompute("3")) == [3]

    assert normalize(s.diffWaysToCompute("1+1+1")) == [3, 3]

    assert normalize(s.diffWaysToCompute("4*2-1")) == [4, 7]

    print("all tests passed")

run_tests()