Different Ways to Add Parentheses: Divide and Conquer Expressions

Given a string expression containing numbers and the operators +, -, and *, return all possible results from computing every different way to group the numbers and operators. You may return the results in any order.

This is LeetCode 241: Different Ways to Add Parentheses. For example, given "2*3-4*5", there are multiple ways to place parentheses: ((2*3)-(4*5)) evaluates to -14, while (2*(3-(4*5))) gives -34. Your job is to find every possible evaluation.

The key insight is that every valid grouping splits the expression at exactly one operator at the top level. That operator becomes the "root" of the evaluation, and the left and right sides become independent sub-problems. This naturally leads to a divide and conquer approach.

The divide and conquer idea

Think about what happens when you choose a single operator as the "last" operation to evaluate. Everything to the left of that operator must be fully evaluated first, and everything to the right must be fully evaluated first. Then you combine the two results using that operator.

Since the left and right halves can themselves be parenthesized in multiple ways, each half may produce multiple possible values. You need to combine every possible left result with every possible right result.

The algorithm becomes:

1. Scan through the expression looking for operators (+, -, *)
2. For each operator found, split the expression into a left part and a right part
3. Recursively compute all possible results for the left part
4. Recursively compute all possible results for the right part
5. Combine every left result with every right result using the operator
6. If no operator was found, the expression is a single number, so return it directly

Python solution

def diff_ways_to_compute(expression):
    results = []

    for i, char in enumerate(expression):
        if char in "+-*":
            left = diff_ways_to_compute(expression[:i])
            right = diff_ways_to_compute(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)

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

    return results

The function iterates over every character in the expression. When it finds an operator, it splits the string into two halves, recursively solves both, and combines all pairs. If after scanning the entire expression no operator was found, that means the expression is a pure number, so it gets converted to an integer and returned as the sole result.

Step-by-step walkthrough

Let's trace through "2*3-4*5" to see how the recursion unfolds:

Notice how the three top-level splits fan out into different recursive paths. The left sub-expression "3-4*5" itself has two operators, so it produces four results. The right sub-expression "2*3-4" produces two results. Each sub-problem follows the exact same splitting logic all the way down to single numbers.

Complexity analysis

Here n is the number of operators in the expression. The number of distinct parenthesizations of n operators follows the Catalan number sequence, which grows exponentially. Each parenthesization produces a result, and we enumerate all of them. The space complexity accounts for storing all results and the recursion stack.

The building blocks

This problem is a clean example of the divide and conquer on expressions pattern. The core idea is: for every operator, split the problem into two halves, solve each half recursively, and combine all possible results.

Operator-based splitting. Instead of splitting at an index in an array, you split at each operator in a string. The left and right halves are themselves valid expressions. This is different from typical array partitioning because the split points are determined by the operators, not by arbitrary indices.

Cartesian product of sub-results. When the left half produces m results and the right half produces n results, you generate all m * n combinations. This "every pair" combination pattern appears whenever two independent sub-problems contribute to the final answer.

Catalan number structure. The number of ways to fully parenthesize an expression with n operators is the nth Catalan number. This is the same counting structure behind Unique Binary Search Trees and Generate Parentheses. Once you recognize the Catalan connection, the exponential nature of the output becomes expected rather than surprising.

Edge cases to watch for

• Single number: the expression "42" has no operators, so the only result is [42]. The base case handles this.
• Two numbers, one operator: "3-1" has one split point, producing [2].
• Negative intermediate results: sub-expressions like "3-4" evaluate to -1. Your combination logic must handle negative numbers correctly.
• Leading zeros in numbers: the problem guarantees valid input, but expressions like "10+5" contain multi-digit numbers. Using int(expression) in the base case handles this naturally.
• All same operators: "1+1+1+1" still follows the same recursive splitting. The number of results equals the Catalan number for the operator count.

From understanding to recall

Walking through this problem once makes the divide and conquer idea clear. But reproducing the solution from memory during an interview is a different challenge. The tricky part is remembering the structure: scan for operators, split at each one, recurse on both halves, combine with a nested loop, and handle the base case when no operator is found.

Spaced repetition helps bridge that gap. By revisiting the operator-splitting pattern at increasing intervals, you build the muscle memory to write this recursive structure without hesitation. The divide and conquer on expressions pattern is one of many reusable building blocks that transfer across problems.

Related posts

• Generate Parentheses - Another problem rooted in Catalan number structure, generating all valid parenthesizations through backtracking
• Unique Binary Search Trees - Counting structures using the same root-splitting recurrence that drives this problem
• Combination Sum - Recursive enumeration of all valid combinations, showing the same "explore every branch" strategy