241. Different Ways to Add Parentheses - Detailed Explanation

In the Java solution, we use a HashMap<String, List<Integer>> to cache results. Before computing a new expression, we check if it exists in memo. The rest of the logic (splitting and combining) remains the same as the brute force approach.

Complexity Analysis: The memoized approach still has to explore all distinct ways to parenthesize the expression (which is inherently exponential in the number of operators), so the worst-case time complexity remains exponential. However, memoization significantly cuts down on redundant computation. Each unique sub-expression (substring of the input) is computed only once. In the worst case, the number of unique sub-expressions is O(N^2) (for an expression of length N, there are that many possible substrings), but practically it’s much less because we only split at operators. The time complexity with memoization is improved roughly to O(Catalan(m)) where m is the number of operators, but without the repetitive multiplier from recomputation. In other words, it still grows quickly (exponential), but it will be several times faster than brute force for larger expressions due to caching. The space complexity is higher for memoization because we store results for sub-expressions in the cache. The cache can contain up to O(N^2) entries of lists of results. In the worst-case scenario, space usage is also exponential in terms of output size (since we might store thousands of results across all sub-expressions). Given the constraints (expression length ≤ 20), this is manageable.

Step-by-Step Walkthrough (Recursive Breakdown)

To better understand the recursion, let’s walk through a smaller example and visualize how the expression is broken down:

Consider the expression "1+2*3". We will find all possible results by adding parentheses in different ways.

• Original expression: "1+2*3"
  • It has two operator positions: index 1 ('+') and index 3 ('*').

Step 1: Choose the first operator ('+' at index 1) as the last operation to perform:

• Split into left = "1" and right = "2*3" around the '+'.

  • Evaluate left part "1": This is just a number, so left results = [1].
  • Evaluate right part "2*3":
    • There is an operator '*' in "2*3". Split into sub-left = "2" and sub-right = "3".
    • sub-left "2" → [2], sub-right "3" → [3] (both are base cases).
    • Combine sub-left and sub-right with *: 2 * 3 = 6, so right results = [6] for the sub-expression "2*3".
  • Now combine the left and right results with the '+' we split on: 1 + 6 = 7.
  • Result from this parenthesization: 7 (which corresponds to the expression 1 + (2*3)).

Step 2: Choose the second operator ('*' at index 3) as the last operation:

• Split into left = "1+2" and right = "3" around the '*'.

  • Evaluate left part "1+2":

    • It has an operator '+'. Split into sub-left = "1" and sub-right = "2".

    • sub-left "1" → [1], sub-right "2" → [2].

    • Combine with +: 1 + 2 = 3, so left results = [3] for "1+2".

  • Evaluate right part "3": it’s a number, so right results = [3].

  • Combine left and right results with *: 3 * 3 = 9.

  • Result from this parenthesization: 9 (which corresponds to the expression (1+2) * 3).

Step 3: Collect all results. From the two different ways we parenthesized "1+2*3", we got results 7 and 9. So the final output list is [7, 9] (order doesn’t matter).

This breakdown shows how the recursion explores different split points. Each indentation level in the above steps represents a recursive call diving into a sub-expression. By following this process, we ensure all possible groupings are covered.

(You can imagine a recursion tree where the root is "1+2*3", which branches into two nodes: one for splitting at '+' and one for splitting at '*'. Each of those branches further breaks down the expression until only numbers remain.)

Common Mistakes

• Not handling single-number expressions: Forgetting to handle the case where the input has no operators. If you don’t return the number itself as a result, your recursion might return an empty list or not terminate. Always include a base case to convert a pure-number string into an integer result.

• Splitting multi-digit numbers incorrectly: Treating each character as a potential number can be problematic. For example, in "10+5", you should recognize "10" as a single number, not "1" and "0" separately. The solutions above handle this by only splitting at operator characters and treating any substring with no operator as a whole number (using parseInt in Java or isdigit() check in Python).

• Recomputing sub-expressions: A brute-force recursive solution without memoization might recalculate the same sub-expression many times, leading to timeouts on larger inputs. A common mistake is not realizing you can cache results. The optimized approach addresses this; forgetting to use it (when needed) can make your solution inefficient.

• Incorrect combination logic: When combining results from left and right sides, ensure you apply the correct operator. It’s easy to mix up the order or the operation itself. Using a clear if/else or switch for '+', '-', '*' as shown in the implementations helps avoid mistakes.

• Not clearing global caches between calls (in certain environments): If you use a static/global memoization map (like the Java solution above), be careful if your code is run multiple times with different inputs. The cache should be cleared for each new input expression. In competitive programming or some platforms, this can cause one test’s results to leak into another if not handled. A simple fix is to define the cache inside the function that does the computation, or re-initialize it at the start of that function.

Edge Cases to Consider

• Single number: e.g. "5". The output should just be [5]. Make sure your base case handles this (and does not try to split further or return an empty list).

• No operators (length 1 input): Same as single number case. Also consider a number with multiple digits and no operators, e.g. "17" should return [17].

• All same operator: e.g. "4-3-2-1" or "2+2+2". These should still produce all combinations even if mathematically some groupings give the same result. For "2+2+2", all parenthesizations yield 6 actually, but your program should output [6,6] (three 6’s, or possibly duplicate values) depending on how the question expects duplicates. Usually, as in the examples, if different parenthesizations yield the same result, that result will appear multiple times in the output list. Verify that your solution does not accidentally remove duplicates.

• Mix of operators: e.g. "2*2-2", "2-2*2", etc., to ensure the order of operations is indeed changed by parentheses. Check that your code isn’t assuming normal operator precedence (it should treat all splits equally regardless of operator precedence, since parentheses can override it).

• Expression resulting in negative or zero: e.g. "2-3-4". Make sure negative results are handled (they will be stored as negative integers in the list, which is fine).

• Largest size input: The expression length can be up to 20. For example, a worst-case might be something like "1*1*1*1*1*1*1*1*1*1" (with 9 operators, 10 numbers) or a mix of plus/minus. Ensure your solution can handle the maximum length (with memoization, it should be fine). Without memoization, it might still run given the constraint, but it will be slower.

Alternative Variations and Related Problems

• Binary Tree Parenthesization: This problem is essentially about forming different binary computation trees. A related concept is Catalan Numbers, which count the number of ways to fully parenthesize an expression (or the number of full binary trees with a given number of leaves). If you found this problem interesting, you might explore the idea of Catalan numbers in problems like Unique Binary Search Trees II (LeetCode 95), where you generate all structurally unique BSTs for n nodes (a similar divide-and-conquer recursion pattern is used there).

• Boolean Parenthesization Problem: A classic variation (not on LeetCode, but common in algorithm courses) is evaluating expressions with boolean values and operators (AND, OR, XOR) and counting the ways to parenthesize them to make the expression true. It uses a similar recursion and dynamic programming approach, but it’s more complex because you track true/false counts.

• Expression Add Operators (LeetCode 282): Although a different problem (there you insert operators to reach a target value), it also involves recursion and exploring different ways to form an expression. It’s a backtracking problem that could be good practice after this one.

• Matrix Chain Multiplication: In algorithm design, the problem of finding the optimal parenthesization of a chain of matrix multiplications is a famous one. While that problem focuses on minimizing the multiplication cost (and uses DP for optimization), it conceptually relates to different ways of parenthesizing a product – showing how rapidly the possibilities grow.