Different Ways to Add Parentheses - Video Solutions

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.