Different Ways to Add Parentheses

Different Ways to Add Parentheses

What is this problem about?

The Different Ways to Add Parentheses coding problem asks you to take a string representing a mathematical expression (like "2-1-1") and return all possible results that can be obtained by grouping the numbers and operators with parentheses in different ways. For example, "(2-1)-1" results in 0, while "2-(1-1)" results in 2. This problem is about exploring the full combinatorial space of operator precedence.

Why is this asked in interviews?

This is a high-signal question for companies like Microsoft, Meta, and Google. It tests your mastery of Recursion and Divide and Conquer interview patterns. It evaluations whether you can break a large expression into smaller sub-expressions and combine their results. Furthermore, it often leads to a discussion on Memoization, as many sub-problems (sub-expressions) are evaluated multiple times, providing an excellent opportunity to show off optimization skills.

Algorithmic pattern used

This problem follows the Divide and Conquer pattern. For any given string, you iterate through every character. If you encounter an operator (+, -, *), you split the string into a "left" part and a "right" part. You then recursively find all possible results for the left part and all possible results for the right part. Finally, you combine every result from the left with every result from the right using the current operator.

Example explanation

Suppose the expression is "2*3-4".

1. Split at '*':
   • Left: "2" $\to$ [2].
   • Right: "3-4" $\to$ [(3-4)] $\to$ [-1].
   • Combine: $2 * (-1) = -2$.
2. Split at '-':
   • Left: "23" $\to$ [(23)] $\to$ [6].
   • Right: "4" $\to$ [4].
   • Combine: $6 - 4 = 2$. Result: [-2, 2].

Common mistakes candidates make

• Missing Base Case: Forgetting to handle strings that contain only a number (no operators), which should simply return that number.
• Inefficiency: Not using a Hash Map for memoization, which leads to exponential time complexity for longer expressions.
• String Slicing: Making errors when dividing the string into substrings based on the operator index.

Interview preparation tip

Whenever you encounter a problem that involves "all possible ways" to group or partition data, think about Divide and Conquer. This logic is similar to finding the number of unique Binary Search Trees or generating combinations. Adding a memoization layer (caching results of sub-strings) is almost always expected by top-tier interviewers.