Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.
The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 104.
Example 1:
Input: expression = "2-1-1" Output: [0,2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2
Example 2:
Input: expression = "2*3-4*5" Output: [-34,-14,-10,-10,10] Explanation: (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 <= 20expression consists of digits and the operator '+', '-', and '*'.[0, 99].'-' or '+' denoting the sign.Problem Overview: You receive a string expression containing numbers and the operators +, -, and *. The task is to compute every possible result produced by inserting parentheses in different valid ways. Each parenthesization changes the evaluation order, so the output is a list of all possible computed values.
Approach 1: Divide and Conquer with Recursion (Time: O(n * 2^n), Space: O(n * 2^n))
Treat every operator as a potential split point. When you encounter an operator while iterating through the expression, divide the string into a left and right subexpression. Recursively compute all possible results for the left side and all results for the right side. Then combine every pair of results using the current operator. For example, if the left side returns [2,3] and the right side returns [4,5], compute all combinations like 2+4, 2+5, 3+4, 3+5. The recursion continues until a substring contains only digits, which becomes the base case. This approach relies heavily on recursion and a classic divide-and-conquer pattern: break the expression at operators, solve subproblems, then merge their results. The downside is repeated work because the same substrings get recomputed many times.
Approach 2: Dynamic Programming with Memoization (Time: O(n * 2^n), Space: O(n * 2^n))
The recursive strategy becomes much faster when you cache results for each substring. Use a dictionary or hash map where the key is the substring and the value is the list of computed results. Before solving a subexpression, check the cache. If results already exist, reuse them immediately instead of recomputing the recursion tree. This drastically reduces repeated work, especially for overlapping subexpressions like "2*3" appearing in multiple splits. The algorithm still explores all valid parenthesizations, but memoization ensures each substring is solved only once. Conceptually this combines dynamic programming with memoization, while still using recursion to generate partitions of the expression. It performs well because most expressions contain many repeated substructures.
Recommended for interviews: Start by explaining the divide-and-conquer recursion. It clearly demonstrates the core insight: every operator splits the problem into two independent subexpressions. After that, mention the optimization with memoization. Interviewers usually expect the memoized version because it shows awareness of overlapping subproblems and dynamic programming techniques while preserving the clean recursive structure.
The problem can be approached by using recursion to divide the expression into sub-expressions at each operator, evaluating each possible combination. For each operator, compute the left and right sub-expressions separately, then combine their results based on the operator. This allows us to explore all possible ways to parenthesize the expression and evaluate it.
This Python solution uses recursion to break down the expression into all possible pairs of sub-expressions partitioned by operators. It recursively computes the result for each pair and combines them according to the operator. The function checks if the expression is a single number and returns it as a list; otherwise, it iterates through the expression characters, recursively calls itself for partitions, and calculates possible results.
Time Complexity: O(2^n) - In the worst case, the algorithm evaluates every partition.
Space Complexity: O(2^n) - due to the recursion depth and storage of intermediate results.
To optimize the recursive approach, we can use memoization to cache the results of subproblems. This avoids redundant evaluations of the same sub-expressions, thereby optimizing the time complexity. We store results of sub-expressions in a hash map and reuse them when the same sub-expression is encountered again.
This Python solution is a memoized version of the recursive approach. It maintains a dictionary to store results of computed sub-expressions. Before calculating a sub-expression, it checks if the result is already available. If so, it reuses the result from the dictionary; otherwise, it calculates and stores it. This method significantly reduces redundant calculations.
Time Complexity: O(n^3) - n^2 subproblems with evaluation cost per subproblem.
Space Complexity: O(n^2) - for storing results of subproblems in a memoization table.
| Approach | Complexity |
|---|---|
| Divide and Conquer with Recursion | Time Complexity: O(2^n) - In the worst case, the algorithm evaluates every partition. |
| Dynamic Programming with Memoization | Time Complexity: O(n^3) - n^2 subproblems with evaluation cost per subproblem. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer Recursion | O(n * 2^n) | O(n * 2^n) | Good for understanding the core idea of splitting expressions at operators |
| Dynamic Programming with Memoization | O(n * 2^n) | O(n * 2^n) | Preferred solution when avoiding repeated computation of the same substrings |
leetcode 241 Different Ways to Add Parentheses • Codebix • 27,144 views views
Watch 9 more video solutions →Practice Different Ways to Add Parentheses with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor