Different Ways to Add Parentheses is a recursive problem that tests how well you can break an expression into subproblems and combine results correctly. You are given a string representing a mathematical expression made up of numbers and operators like +, -, and *.
Your task is to compute all possible results that can be obtained by adding parentheses in different valid ways.
The key detail is that parentheses can change the order of evaluation. You are not asked to return one result or the maximum result. You must return every possible outcome produced by all valid parenthesizations.
For example, the expression 2-1-1 can evaluate to 0 or 2, depending on how parentheses are placed.
This problem often appears in interviews because it checks whether you understand recursion, divide-and-conquer thinking, and how to manage repeated subexpressions.
Why this problem is harder than it looks
At first glance, it seems like you could try all possible parentheses placements directly. But the number of ways to parenthesize an expression grows quickly.
A naive recursive approach also ends up recalculating the same subexpressions many times. For example, the same left or right substring may be evaluated repeatedly under different parenthesis groupings.
The challenge is not just to generate results, but to do so in a structured way that avoids unnecessary recomputation.
Want to explore more coding problem solutions? Check out the Binary Tree Zigzag Level Order Traversal and Online Stock Span coding problem solutions.
The core idea behind the solution
The most natural way to solve this problem is to treat each operator as a possible “split point.”
Whenever you see an operator in the expression, you can imagine placing the final set of parentheses around it. That divides the expression into a left part and a right part.
Once split, the problem becomes recursive:
- Compute all possible results from the left substring
- Compute all possible results from the right substring
- Combine every left result with every right result using the operator
If the expression contains no operators, then it must be a single number. In that case, the only possible result is the number itself.
How recursion builds all possible results
You scan the expression from left to right.
Each time you encounter an operator, you recursively evaluate everything to the left of it and everything to the right of it.
Suppose the left side produces results [a, b] and the right side produces [c, d]. If the operator is *, then the combined results are:
- a * c
- a * d
- b * c
- b * d
You repeat this process for every operator position and collect all results.
By doing this, you systematically explore every valid way to insert parentheses without explicitly generating parentheses strings.
Why memoization matters
Without memoization, the same substrings are evaluated again and again. That leads to exponential time growth and slow performance.
The fix is a simple concept.
Whenever you compute all possible results for a given substring, you store them in a map using the substring as the key.
If the same substring appears again later in the recursion, you return the stored results immediately instead of recomputing them.
This turns a slow recursive solution into a much more efficient one while keeping the logic clean and easy to explain.
Why this approach is correct
Every valid parenthesization has a “last operation” that is evaluated.
By trying every operator as the last operation, you guarantee that every valid evaluation order is covered.
The recursive structure ensures that smaller expressions are solved correctly before being combined into larger ones.
Memoization ensures that correctness does not come at the cost of repeated work.
Performance in simple terms
The number of possible results can grow quickly as the expression gets longer, so the output itself can be large.
The algorithm runs efficiently relative to the size of the output, especially when memoization is used.
Space usage grows with the number of unique substrings stored, which is manageable for typical interview constraints.
Top comments (0)