Problem Description

You are given a string expression containing numbers and operators (+, -, *). Your task is to compute all possible results that can be obtained by grouping the numbers and operators in different ways using parentheses.

For example, if the expression is "2-1-1", you can group it as:

• (2-1)-1 = 0
• 2-(1-1) = 2

So the output would be [0, 2].

The key points to understand:

• You need to find ALL possible ways to add parentheses to the expression
• Each different way of grouping will potentially give a different result
• The operators maintain their standard mathematical precedence within each grouping
• You can return the results in any order
• The expression will only contain single or multi-digit numbers and the operators +, -, *

The solution uses a divide-and-conquer approach with memoization. For each operator in the expression, it splits the expression into left and right parts, recursively computes all possible results for each part, and then combines them using the operator. The base case is when the expression contains only a number (no operators), in which case it returns that number as the only result.

The @cache decorator helps avoid recomputing results for the same sub-expressions, improving efficiency. The algorithm systematically explores all possible ways to split the expression at each operator position, ensuring all possible groupings are considered.

Intuition

When we see an expression like "2*3-4*5", we need to think about all the different ways we can evaluate it by adding parentheses. The key insight is that every way of fully parenthesizing the expression corresponds to choosing which operator to evaluate last.

Think about it this way: in any fully parenthesized expression, there's always one operator that gets evaluated last. For example:

• In ((2*3)-(4*5)), the - is evaluated last
• In (2*(3-(4*5))), the first * is evaluated last
• In ((2*(3-4))*5), the last * is evaluated last

This naturally leads to a recursive approach: for each operator in our expression, we can treat it as the "last" operator to be evaluated. This splits our expression into two parts - everything to the left of this operator and everything to the right.

For example, if we choose the - in "2*3-4*5" as our last operator:

• Left part: "2*3"
• Right part: "4*5"

Now here's the recursive insight: we need to find all possible results for the left part and all possible results for the right part. Then, we combine each result from the left with each result from the right using our chosen operator.

The recursion continues until we hit a base case - when our expression is just a number with no operators. At that point, the only possible result is the number itself.

This approach ensures we explore all possible ways of parenthesizing because:

1. We try every operator as a potential "last" operator
2. For each split, we recursively explore all possibilities for both sub-expressions
3. We combine all possible left results with all possible right results

The memoization (@cache) is a natural optimization since we might encounter the same sub-expression multiple times through different recursive paths.

Solution Approach

The solution implements a divide-and-conquer algorithm with memoization using Python's @cache decorator. Let's walk through the implementation step by step:

1. Main Function Structure: The solution defines a nested recursive function dfs(exp) that processes any expression string and returns a list of all possible results.

2. Base Case:

if exp.isdigit():
    return [int(exp)]

When the expression contains only digits (no operators), we've reached our base case. We simply return a list containing that single number.

3. Recursive Case: For expressions containing operators, we iterate through each character:

for i, c in enumerate(exp):
    if c in '-+*':

When we find an operator, we treat it as the potential "last" operator to be evaluated.

4. Divide Step:

left, right = dfs(exp[:i]), dfs(exp[i + 1 :])

We split the expression at the operator position:

• exp[:i] gives us everything before the operator
• exp[i + 1:] gives us everything after the operator Both sub-expressions are recursively evaluated to get all their possible results.

5. Conquer Step:

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)

We combine every result from the left sub-expression with every result from the right sub-expression using the current operator. This ensures we capture all possible combinations.

6. Memoization: The @cache decorator automatically memoizes the results. If dfs is called with the same expression string multiple times, it returns the cached result instead of recomputing it. This is crucial for efficiency since the same sub-expression can appear in multiple recursive branches.

Time Complexity Analysis: The number of possible results follows the Catalan number sequence, which grows exponentially. For an expression with n operators, the time complexity is approximately O(2^n) in the worst case, though memoization helps avoid redundant calculations.

Space Complexity: The space complexity includes the recursion stack depth O(n) and the space to store all possible results, which can be up to O(2^n) in total.

Example Walkthrough

Let's trace through the expression "2*3-4" to see how the algorithm finds all possible results.

Initial Call: dfs("2*3-4")

The expression contains operators, so we iterate through each character:

1. When i=1, c='*' (first operator):

   • Split: left = dfs("2"), right = dfs("3-4")
   • dfs("2") is just a number, returns [2]
   • dfs("3-4") needs further processing:
     • At i=1, c='-': Split into dfs("3") and dfs("4")
     • dfs("3") returns [3]
     • dfs("4") returns [4]
     • Combine: 3 - 4 = -1
     • Returns [-1]
   • Now combine results from "2" and "3-4" using '*':
     • 2 * (-1) = -2
   • This grouping represents: 2 * (3 - 4) = -2

2. When i=3, c='-' (second operator):

   • Split: left = dfs("2*3"), right = dfs("4")
   • dfs("4") is just a number, returns [4]
   • dfs("2*3") needs processing:
     • At i=1, c='*': Split into dfs("2") and dfs("3")
     • dfs("2") returns [2]
     • dfs("3") returns [3]
     • Combine: 2 * 3 = 6
     • Returns [6]
   • Now combine results from "2*3" and "4" using '-':
     • 6 - 4 = 2
   • This grouping represents: (2 * 3) - 4 = 2

Final Result: [-2, 2]

The algorithm found both possible ways to parenthesize:

• 2 * (3 - 4) = 2 * (-1) = -2
• (2 * 3) - 4 = 6 - 4 = 2

Note how memoization helps: when we call dfs("2") multiple times in different recursive branches, the cached result is returned instantly after the first computation.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * 2^n)

The algorithm uses divide-and-conquer with memoization. For each operator in the expression, we split it into left and right subexpressions and recursively compute all possible results. In the worst case:

• There are n operators in the expression
• Each way of parenthesizing corresponds to a unique binary tree structure
• The number of ways to parenthesize an expression with n operators is the n-th Catalan number, which is approximately O(4^n / n^(3/2))
• However, with memoization (@cache), each unique substring is computed only once
• There are O(n^2) possible substrings of the input expression
• For each substring with k operators, we iterate through all operators and combine results from left and right subproblems
• The combination step for each split point takes O(left_results * right_results) time
• In the worst case, this leads to O(n * 2^n) time complexity, where n is the length of the expression

Space Complexity: O(n^2 * 2^n)

The space complexity consists of:

• Memoization cache: O(n^2) unique substrings, and each substring can produce up to O(2^n) different results (Catalan number bound), giving us O(n^2 * 2^n) for storing all cached results
• Recursion stack depth: O(n) in the worst case when the expression is parsed linearly
• Temporary storage for results: Each recursive call stores an ans list that can contain up to O(2^n) results

The dominant factor is the memoization cache, making the overall space complexity O(n^2 * 2^n).

Common Pitfalls

1. Incorrect Handling of Multi-Digit Numbers

One of the most common mistakes is treating each digit as a separate number instead of recognizing multi-digit numbers. For example, in the expression "23-4*5", the 23 should be treated as a single number, not as 2 and 3.

Incorrect Approach:

# Wrong: This would treat "23" as separate digits
for i, c in enumerate(expression):
    if c.isdigit():
        # Process each digit separately - WRONG!
        results.append(int(c))

Correct Solution: The provided code handles this correctly by:

• Using exp.isdigit() to check if the entire substring is a number
• Only splitting at operator positions, preserving multi-digit numbers intact
• The recursive calls with exp[:i] and exp[i+1:] maintain number integrity

2. Missing Base Case for Multi-Digit Numbers

Another pitfall is having an incomplete base case that only checks for single digits:

Incorrect Base Case:

# Wrong: Only handles single digits
if len(exp) == 1 and exp.isdigit():
    return [int(exp)]

Correct Solution:

# Correct: Handles any length number
if exp.isdigit():
    return [int(exp)]

This correctly identifies strings like "123" as base cases and converts them to integers.

3. Forgetting to Cache or Using Incorrect Memoization

Without proper memoization, the algorithm becomes extremely inefficient due to redundant calculations:

Inefficient Approach:

def compute_ways(expr: str) -> List[int]:
    # No @cache decorator - will recompute same subproblems
    if expr.isdigit():
        return [int(expr)]
    # ... rest of the code

Issues with Manual Memoization:

# Wrong: Using mutable default argument
def compute_ways(expr: str, memo={}) -> List[int]:
    if expr in memo:
        return memo[expr]
    # ... computation
    memo[expr] = results
    return results  # Dangerous: memo persists across function calls

Correct Solution: Using @cache decorator ensures proper memoization without the pitfalls of manual implementation.

4. Incorrect Operator Detection

A subtle but critical mistake is incorrectly identifying operator positions:

Wrong Approach:

# This might miss operators or include wrong characters
operators = []
for i in range(len(expression)):
    if not expression[i].isdigit():
        operators.append(i)

Correct Solution:

for i, c in enumerate(exp):
    if c in '-+*':  # Explicitly check for valid operators

5. Modifying the Results List Instead of Creating New Ones

When dealing with recursive calls and memoization, modifying shared lists can lead to incorrect results:

Problematic Code:

@cache
def compute_ways(expr: str) -> List[int]:
    results = []  # This is fine
    # ... computation
    return results  # Returning a new list each time is correct

What to Avoid:

# Wrong: Modifying a shared list
global_results = []
def compute_ways(expr: str):
    global_results.clear()  # Don't do this!
    # ... append to global_results
    return global_results

The correct approach creates a fresh list for each recursive call, ensuring independence between different branches of computation.