LeetCode 241 - Different Ways to Add Parentheses

LeetCode Problem 241

Difficulty: 🟡 Medium
Topics: Math, String, Dynamic Programming, Recursion, Memoization

Solution

Problem Understanding

The problem gives us a mathematical expression as a string containing integers and arithmetic operators (+, -, *). We are asked to compute all possible results that can be obtained by inserting parentheses in every valid way.

The key detail is that we are not evaluating the expression using normal operator precedence. Instead, we consider every possible way to group operations using parentheses. Each distinct grouping may produce a different result, and we must return all of them.

For example, consider the expression "2-1-1".

If we parenthesize it as:

((2-1)-1)

we get:

0

If we parenthesize it as:

(2-(1-1))

we get:

2

So the final answer is:

[0, 2]

The input consists of:

• Positive integers from 0 to 99
• Operators: +, -, and *
• Expression length up to 20

The output should contain all possible computed values resulting from different parenthesizations. Duplicate results are allowed because different groupings can produce the same numeric value.

The constraints provide several important clues.

First, the expression length is relatively small (<= 20). This strongly suggests that an exponential or recursive approach may be acceptable.

Second, the number of returned results is capped at 10^4, which implies that the search space is manageable with memoization.

Third, numbers can have multiple digits, so we cannot assume every character is an independent number. We must properly parse substrings like "12" or "99".

Several edge cases are worth identifying upfront.

A naive implementation might fail when the expression contains only a single number, because there are no operators to split on. For example, "42" should return [42].

Another subtle case is repeated subexpressions. During recursive splitting, the same substring may be recomputed many times, creating severe redundancy. For example, "2*3-4*5" repeatedly evaluates "4*5" and "2*3". Without memoization, performance degrades quickly.

Finally, duplicate outputs must be preserved. If two different parenthesizations produce -10, both occurrences should remain in the result.

Approaches

Brute Force Recursive Enumeration

The most direct approach is to recursively try every possible operator as a splitting point.

For every operator in the expression:

1. Split the expression into a left and right subexpression.
2. Recursively compute all possible results for the left side.
3. Recursively compute all possible results for the right side.
4. Combine every left result with every right result using the current operator.

If the substring contains no operator, it is simply a number, so we return that value.

This approach is correct because every valid parenthesization must choose some operator as the final operation. By recursively exploring all operator positions, we enumerate every possible computation tree.

However, this method recomputes identical subproblems repeatedly. Consider:

2*3-4*5

The substring "4*5" may be solved multiple times from different recursive paths. Since recursive branching grows rapidly, repeated work becomes expensive.

Optimal Approach, Divide and Conquer with Memoization

The key observation is that this problem has overlapping subproblems.

Whenever we compute all possible values for a substring, the answer will always be the same. Instead of recomputing it repeatedly, we can cache the result.

We use:

• Divide and conquer to split expressions around operators.
• Memoization to store results for previously solved substrings.

The recursive structure naturally models expression parenthesization:

• Each operator represents a possible root of the computation tree.
• Left and right subexpressions are solved independently.
• Results are combined pairwise.

Memoization turns exponential recomputation into a much more efficient dynamic programming style solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential, approximately O(2^n) to O(Cn)	O(Cn)	Recomputes identical substrings repeatedly
Optimal	O(n × Cn)	O(n × Cn)	Memoization prevents repeated computation of subexpressions

Here, Cn refers to the Catalan-number style growth of parenthesization possibilities.

Algorithm Walkthrough

1. Create a recursive helper function that takes a substring of the expression and returns all possible computed results for that substring.
2. Before computing anything, check whether this substring already exists in a memoization map. If it does, return the cached result immediately. This avoids redundant recomputation.
3. Scan the substring character by character.
4. Whenever an operator (+, -, *) is found, split the expression into:

• Left substring
• Right substring

5. Recursively compute all possible results for both halves.
6. Combine every left result with every right result:

• If the operator is +, add them.
• If the operator is -, subtract them.
• If the operator is *, multiply them.

7. Append every computed value to the result list.
8. After scanning the entire substring, check whether no operator was found. If so, the substring represents a number, so convert it to an integer and return it as a single-element list.
9. Store the computed result in the memoization map before returning it.
10. Start the recursion using the full expression.

Why it works

The algorithm works because every valid parenthesization has exactly one operator that is evaluated last. By recursively choosing every operator as the final split point, we enumerate all valid computation trees. Since the left and right halves are solved independently and combined exhaustively, no valid result is missed. Memoization preserves correctness because the value of a substring never changes, so reusing cached results is always safe.

Python Solution

from typing import List

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        memo = {}

        def compute(sub_expression: str) -> List[int]:
            if sub_expression in memo:
                return memo[sub_expression]

            results = []

            for index, char in enumerate(sub_expression):
                if char in "+-*":
                    left_results = compute(sub_expression[:index])
                    right_results = compute(sub_expression[index + 1:])

                    for left_value in left_results:
                        for right_value in right_results:
                            if char == "+":
                                results.append(left_value + right_value)
                            elif char == "-":
                                results.append(left_value - right_value)
                            else:
                                results.append(left_value * right_value)

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

            memo[sub_expression] = results
            return results

        return compute(expression)

The implementation starts by creating a memo dictionary that maps substrings to their computed results. This serves as our cache.

The nested compute() function performs the recursive divide-and-conquer logic. It accepts a substring and immediately checks whether it has already been solved. If so, the cached result is returned.

The function then scans every character. When it encounters an operator, it recursively evaluates the left and right portions of the expression.

Since each side may produce multiple possible results, we use nested loops to combine every pair. This ensures all valid parenthesizations are represented.

If no operator is found, the substring must be a number. We convert it to an integer and return it as a one-element list.

Finally, we cache the computed result before returning it, ensuring future calls for the same substring are constant-time lookups.

Go Solution

func diffWaysToCompute(expression string) []int {
	memo := make(map[string][]int)

	var compute func(string) []int

	compute = func(subExpression string) []int {
		if result, exists := memo[subExpression]; exists {
			return result
		}

		results := []int{}

		for i, ch := range subExpression {
			if ch == '+' || ch == '-' || ch == '*' {
				leftResults := compute(subExpression[:i])
				rightResults := compute(subExpression[i+1:])

				for _, leftValue := range leftResults {
					for _, rightValue := range rightResults {
						switch ch {
						case '+':
							results = append(results, leftValue+rightValue)
						case '-':
							results = append(results, leftValue-rightValue)
						case '*':
							results = append(results, leftValue*rightValue)
						}
					}
				}
			}
		}

		if len(results) == 0 {
			number := 0
			for _, ch := range subExpression {
				number = number*10 + int(ch-'0')
			}
			results = append(results, number)
		}

		memo[subExpression] = results
		return results
	}

	return compute(expression)
}

The Go implementation follows the same recursive memoized structure as Python.

One notable difference is number parsing. Instead of calling a built-in conversion helper, we manually construct the integer digit by digit. This avoids additional imports and keeps the solution self-contained.

Go slices naturally represent dynamic arrays, so results are accumulated using append. The memoization map stores slices of integers keyed by substring.

Unlike Python, Go distinguishes between nil and empty slices, but here we explicitly initialize results := []int{} so behavior remains predictable.

Worked Examples

Example 1

Input:

"2-1-1"

We recursively split at every operator.

Split at index 1 (-)

Left:

"2"

Right:

"1-1"

"2" becomes:

[2]

Now solve "1-1":

Split	Left	Right	Result
1 - 1	[1]	[1]	[0]

Combine:

2 - 0 = 2

Result so far:

[2]

Split at index 3 (-)

Left:

"2-1"

Right:

"1"

"2-1":

Split	Left	Right	Result
2 - 1	[2]	[1]	[1]

Combine:

1 - 1 = 0

Final result:

[2, 0]

Order does not matter.

Example 2

Input:

"2*3-4*5"

Possible split positions:

Operator Index	Expression Split
1	`2
3	`2*3
5	`2*3-4

Split at * (index 1)

Left:

[2]

Right:

"3-4*5"

Recursive results for "3-4*5":

[-17, -5]

Combine:

2 * -17 = -34
2 * -5 = -10

Split at - (index 3)

Left:

"2*3" -> [6]

Right:

"4*5" -> [20]

Combine:

6 - 20 = -14

Split at * (index 5)

Left:

"2*3-4" -> [-2, 2]

Right:

[5]

Combine:

-2 * 5 = -10
2 * 5 = 10

Final answer:

[-34, -14, -10, -10, 10]

Notice that -10 appears twice because two different parenthesizations produce it.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × Cn)	Each subexpression is solved once, and combinations follow Catalan-style growth
Space	O(n × Cn)	Memoization storage plus recursive call stack and generated results

The dominant factor is the number of possible parenthesizations, which follows Catalan-number growth. Memoization ensures each substring is computed only once, eliminating repeated recursion. Since every valid result must still be generated, the algorithm cannot avoid combinatorial output size.

Test Cases

solution = Solution()

# Provided example 1
assert sorted(solution.diffWaysToCompute("2-1-1")) == [0, 2]

# Provided example 2
assert sorted(solution.diffWaysToCompute("2*3-4*5")) == [-34, -14, -10, -10, 10]

# Single number
assert solution.diffWaysToCompute("42") == [42]  # no operators

# Single operation
assert solution.diffWaysToCompute("3+2") == [5]  # simple addition

# Multiple identical results
assert sorted(solution.diffWaysToCompute("1+1+1")) == [3, 3]  # duplicates preserved

# Multiplication chain
assert sorted(solution.diffWaysToCompute("2*3*4")) == [24, 24]  # multiple parenthesizations

# Zero handling
assert sorted(solution.diffWaysToCompute("0*1+2")) == [0, 2]  # multiplication by zero

# Multi-digit numbers
assert solution.diffWaysToCompute("10+5") == [15]  # number parsing

# Mixed operators
assert sorted(solution.diffWaysToCompute("5-3+1")) == [1, 3]  # different grouping outcomes

# Longer expression
assert len(solution.diffWaysToCompute("1+2+3+4")) == 5  # Catalan-style growth

Test	Why
"2-1-1"	Validates provided subtraction example
"2*3-4*5"	Validates complex recursive splitting
"42"	Ensures single-number base case works
"3+2"	Verifies simplest operator handling
"1+1+1"	Confirms duplicate outputs are preserved
"2*3*4"	Tests repeated parenthesizations
"0*1+2"	Ensures zero arithmetic behaves correctly
"10+5"	Verifies multi-digit number parsing
"5-3+1"	Tests mixed operator ordering
"1+2+3+4"	Stresses recursive branching

Edge Cases

Expression Contains Only a Number

An expression like "42" has no operators, meaning there is nothing to split recursively. A buggy implementation might return an empty list because no recursive branches occur.

This implementation handles the case by checking whether any operator was encountered. If none exist, the substring is converted directly into an integer and returned as a single-element list.

Multi-Digit Numbers

A common mistake is assuming every character is an independent operand. For example, "12+34" should be interpreted as two numbers, not four separate digits.

Our implementation avoids this issue because recursive splitting only occurs at operators. If a substring contains no operator, the entire substring is parsed as one integer.

Duplicate Results

Different parenthesizations may produce the same numeric value. For example:

"2*3*4"

Both:

((2*3)*4)

and

(2*(3*4))

produce 24.

A buggy implementation might accidentally remove duplicates by using a set. This solution deliberately stores results in a list, preserving duplicate values exactly as required by the problem.

Repeated Subexpressions

Expressions like "2*3-4*5" repeatedly reuse smaller segments such as "4*5".

Without memoization, these subexpressions would be recalculated many times, leading to exponential slowdowns. The memo dictionary ensures every substring is solved once and reused thereafter.