#241

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Different Ways to Add Parentheses

Solve Different Ways to Add Parentheses by splitting on each operator and memoizing every subexpression result list.

math string dynamic programming recursion memoization

Problem Statement

You are given an arithmetic expression as a string, built from non-negative integers and the operators +, -, and *. Your job is to return every value that can appear when the expression is parenthesized in all valid ways. The result list can be returned in any order, and duplicate values should stay if different parenthesizations produce the same number.

A useful small case is expression = "2-1-1", where one grouping gives ((2-1)-1) = 0 and another gives (2-(1-1)) = 2, so the output is [0,2]. A larger case like "2 3-4 5" shows why this problem is not about normal precedence rules: each operator can be chosen as the last operation of a subexpression, and the test data is bounded so every final value fits in 32-bit integer range.

Examples

Example 1

Input: expression = "2-1-1"

Output: [0,2]

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

Example 2

Input: expression = "2*3-4*5"

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

(2*(3-(4 5))) = -34 ((2 3)-(4 5)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((2 3)-4)*5) = 10

Constraints

1 <= expression.length <= 20
expression consists of digits and the operator '+', '-', and '*'.
All the integer values in the input expression are in the range [0, 99].
The integer values in the input expression do not have a leading '-' or '+' denoting the sign.

Solution Approach

1. Treat each operator as a state split

For Different Ways to Add Parentheses, the core state transition is: results(expression[l..r]) equals the union of combining every result from the left side with every result from the right side for each operator inside the range. If a substring contains no operator, it is a base case and evaluates to one integer. This makes the problem a natural divide-and-conquer DP over subexpressions, not a precedence parser.

2. Recursively combine left and right result sets

Scan the current substring. Whenever you see +, -, or *, split the expression into left and right parts, recursively collect all possible values from both sides, then take the Cartesian product of those two lists and apply the operator to each pair. For "2-1-1", splitting at the first - produces 2 and all results of "1-1", while splitting at the second - produces all results of "2-1" and 1; those two split positions are exactly why the answer includes both 0 and 2.

3. Memoize each substring to remove repeated work

The failure mode in this problem is recomputing the same subexpression from multiple parenthesization paths. Cache the result list for each substring or index range, so repeated calls like the middle piece of "2 3-4 5" are solved once and reused. That memo table is the dynamic programming layer: each state stores every possible value, not just one best value.

Complexity Analysis

Metric	Value
Time	O(n \cdot 2^n)
Space	O(n^2 \cdot 2^n)

With memoization, each subexpression is solved once, but combining all left and right result lists can still grow quickly because this problem must materialize every valid outcome. A standard bound for Different Ways to Add Parentheses is O(n · 2^n) time and O(n^2 · 2^n) space, where the extra growth comes from storing and merging many intermediate result lists across substring states.

What Interviewers Usually Probe

They expect you to say each operator can be the final operation, which defines the subproblem split.
They want memoization once you notice the same substring is evaluated from multiple recursive branches.
They may check whether you preserve duplicate results, because different parenthesizations can yield the same value.

Common Pitfalls or Variants

Common pitfalls

Evaluating with normal arithmetic precedence instead of generating every parenthesization misses valid outputs like the alternate result in "2-1-1".
Returning a set instead of a list incorrectly removes duplicates, which breaks cases like "2 3-4 5" where -10 appears twice.
Memoizing only one number per substring is wrong because each subexpression in Different Ways to Add Parentheses can produce many values.

Follow-up variants

Return the number of distinct results instead of the full result list, which changes storage but keeps the same split pattern.
Support additional operators such as division, where you must define integer behavior and guard invalid splits like divide-by-zero.
Solve the same recurrence with index-based DP over tokens instead of substring slicing to reduce string handling overhead.

FAQ

What is the best pattern for Different Ways to Add Parentheses?

Use memoized divide-and-conquer over subexpressions. In dynamic programming terms, each substring is a state, and every operator inside that substring defines a transition that combines all left results with all right results.

Why is this considered dynamic programming if the solution is recursive?

The recursion defines the state transitions, but memoization is what makes it dynamic programming. Each substring or index range is solved once, and its full list of possible values is reused anywhere that state appears again.

Why do duplicate numbers stay in the output?

Because the problem asks for all possible results from all different parenthesizations, not just unique values. Two different grouping choices can evaluate to the same number, and those should both contribute to the returned list.

How do I know when a substring is a base case?

If the current piece contains no operator, it is just one integer and should return a single-element list containing that parsed value. This base case is what lets larger splits build results upward.

Can I build a bottom-up table for this problem instead of recursion?

Yes, you can tokenize numbers and operators and fill a DP table by interval length. The recurrence is the same as the recursive solution, but top-down memoization is usually shorter and easier to implement correctly for problem 241.

terminal

Solution

Solution 1

#### Python3

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        @cache
        def dfs(exp):
            if exp.isdigit():
                return [int(exp)]
            ans = []
            for i, c in enumerate(exp):
                if c in '-+*':
                    left, right = dfs(exp[:i]), dfs(exp[i + 1 :])
                    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)
            return ans

        return dfs(expression)

Continue Practicing

#224 basic calculator #140 word break ii #139 word break