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 ways. Each parenthesization changes the evaluation order, so you must explore all valid computation trees.

Approach 1: Divide and Conquer with Recursion (Time: O(n * 2^n), Space: O(2^n))

Treat every operator as a potential split point. Scan the expression and whenever you encounter an operator, split the string into left and right subexpressions. Recursively compute all results from the left part and all results from the right part, then combine them using the current operator. For example, if the left side produces values a and the right side produces b, compute a + b, a - b, or a * b depending on the operator. This approach naturally forms a recursion tree similar to building all binary expression trees. The number of combinations grows exponentially because each operator introduces new ways to group the expression.

Approach 2: Dynamic Programming with Memoization (Time: O(n * 2^n), Space: O(n * 2^n))

The recursive solution recomputes the same subexpressions multiple times. Memoization removes that redundancy. Store the computed results for every substring of the expression in a hash map keyed by the substring. When recursion encounters the same subexpression again, return the cached results instead of recomputing them. The algorithm still explores every valid partition of the expression, but repeated work disappears. This optimization drastically improves practical performance for longer expressions. Conceptually this is a top‑down dynamic programming strategy layered on top of a recursion divide‑and‑conquer structure, with cached subproblem results using memoization.

Recommended for interviews: Start with the divide-and-conquer explanation since it mirrors how the expression can be split at every operator. Then add memoization to avoid recomputing subexpressions. Interviewers expect the memoized version because it demonstrates recognition of overlapping subproblems and the ability to optimize recursive solutions.