# LeetCode 241: Different Ways to Add Parentheses ## Problem Restatement We are given a string `expression` containing: - Non-negative integers - Operators: - `+` - `-` - `*` We need to compute all possible results from adding parentheses in every valid way. The answer may contain duplicate values if different parenthesizations produce the same result. LeetCode examples include: ```text Input: expression = "2-1-1" Output: [0,2] ``` and: ```text Input: expression = "2*3-4*5" Output: [-34,-14,-10,-10,10] ``` The expression length is at most `20`. ([leetcode.com](https://leetcode.com/problems/different-ways-to-add-parentheses/?utm_source=chatgpt.com)) ## Input and Output | Item | Meaning | |---|---| | Input | Arithmetic expression string | | Output | List of all possible results | | Operators | `+`, `-`, `*` | | Parentheses | We choose all valid placements implicitly | | Duplicates | Allowed | Function shape: ```python class Solution: def diffWaysToCompute(self, expression: str) -> list[int]: ... ``` ## Examples Example 1: ```text Input: "2-1-1" Output: [0,2] ``` Two valid parenthesizations exist. ### First way ```text (2 - 1) - 1 ``` Result: ```text 0 ``` ### Second way ```text 2 - (1 - 1) ``` Result: ```text 2 ``` So the answer is: ```text [0, 2] ``` Example 2: ```text Input: "2*3-4*5" ``` Different parenthesizations produce: ```text -34 -14 -10 -10 10 ``` Duplicates are kept. ## First Thought: Try Every Parenthesization The expression can split at every operator. For: ```text 2*3-4*5 ``` possible top-level splits are: ```text 2 | * | 3-4*5 2*3 | - | 4*5 2*3-4 | * | 5 ``` Each split creates: - A left subexpression - A right subexpression If we know all possible results for both sides, we can combine them using the operator. This naturally suggests recursion. ## Key Insight Every operator can become the final operation of some parenthesization. For example: ```text 2*3-4*5 ``` If we choose `-` as the final operation: ```text (2*3) - (4*5) ``` Then: - The left side itself may have multiple results. - The right side itself may have multiple results. So the problem breaks into smaller versions of the same problem. This is classic divide and conquer recursion. ## Recursive Structure Define: ```python solve(expr) ``` to return: ```text all possible results of expr ``` Then for every operator: 1. Solve the left part recursively. 2. Solve the right part recursively. 3. Combine every left result with every right result. ## Base Case If the expression contains no operator, then it is just a number. Example: ```text "123" ``` Result: ```text [123] ``` This becomes the recursion base case. ## Combining Results Suppose: ```text left_results = [2, 3] right_results = [4, 5] operator = * ``` Then all combinations are: ```text 2 * 4 = 8 2 * 5 = 10 3 * 4 = 12 3 * 5 = 15 ``` So the combined results are: ```text [8, 10, 12, 15] ``` ## Algorithm For an expression: 1. Initialize an empty result list. 2. Scan the expression character by character. 3. Whenever we see an operator: - Split the expression into left and right parts. - Recursively compute all results for both parts. - Combine every left result with every right result. 4. If no operator exists: - Convert the expression to an integer. - Return it as a single-element list. ## Walkthrough Use: ```text "2-1-1" ``` Possible splits: ### Split at first `-` ```text 2 | - | 1-1 ``` Left results: ```text [2] ``` Right results: ```text [0] ``` Combine: ```text 2 - 0 = 2 ``` ### Split at second `-` ```text 2-1 | - | 1 ``` Left results: ```text [1] ``` Right results: ```text [1] ``` Combine: ```text 1 - 1 = 0 ``` Final answer: ```text [2, 0] ``` Order does not matter. ## Correctness We prove the algorithm returns exactly all possible results. Every valid parenthesization has some final operation applied last. That final operation corresponds to one operator position in the expression. When the algorithm splits at an operator, it considers all possible results of the left subexpression and all possible results of the right subexpression recursively. By the recursive definition, those recursive calls already contain every valid result for the two subexpressions. The algorithm then combines every left result with every right result using the current operator. Therefore, it generates every valid result whose final operation is that operator. Since the algorithm repeats this for every operator position, it generates results for every possible parenthesization. The base case handles pure numbers correctly by returning the numeric value itself. Therefore, the algorithm returns exactly all valid computation results. ## Complexity The number of possible parenthesizations grows exponentially. | Metric | Value | |---|---| | Time | Exponential | | Space | Exponential recursion/result storage | The exact count is related to Catalan numbers. Because many subexpressions repeat, memoization can significantly improve performance. ## Implementation Without Memoization ```python class Solution: def diffWaysToCompute(self, expression: str) -> list[int]: results = [] for i, ch in enumerate(expression): if ch in "+-*": left_results = self.diffWaysToCompute(expression[:i]) right_results = self.diffWaysToCompute(expression[i + 1:]) for left in left_results: for right in right_results: if ch == "+": results.append(left + right) elif ch == "-": results.append(left - right) else: results.append(left * right) if not results: results.append(int(expression)) return results ``` ## Code Explanation We scan the expression: ```python for i, ch in enumerate(expression): ``` Whenever we find an operator: ```python if ch in "+-*": ``` we split the expression: ```python expression[:i] expression[i + 1:] ``` Then recursively compute all possible results for both sides: ```python left_results = self.diffWaysToCompute(expression[:i]) right_results = self.diffWaysToCompute(expression[i + 1:]) ``` Now combine every pair: ```python for left in left_results: for right in right_results: ``` Apply the operator: ```python if ch == "+": results.append(left + right) ``` and similarly for `-` and `*`. If no operator was found: ```python if not results: ``` then the expression is just a number: ```python results.append(int(expression)) ``` ## Memoization Optimization Many subexpressions repeat. For example: ```text 2*3-4*5 ``` may repeatedly solve: ```text "4*5" ``` Memoization stores already-computed results. ## Optimized Implementation ```python from functools import cache class Solution: @cache def diffWaysToCompute(self, expression: str) -> list[int]: results = [] for i, ch in enumerate(expression): if ch in "+-*": left_results = self.diffWaysToCompute(expression[:i]) right_results = self.diffWaysToCompute(expression[i + 1:]) for left in left_results: for right in right_results: if ch == "+": results.append(left + right) elif ch == "-": results.append(left - right) else: results.append(left * right) if not results: results.append(int(expression)) return results ``` The `@cache` decorator remembers previously computed subexpressions automatically. ## Testing ```python def normalize(values): return sorted(values) def run_tests(): s = Solution() assert normalize(s.diffWaysToCompute("2-1-1")) == [0, 2] assert normalize(s.diffWaysToCompute("2*3-4*5")) == [ -34, -14, -10, -10, 10, ] assert normalize(s.diffWaysToCompute("3")) == [3] assert normalize(s.diffWaysToCompute("1+1+1")) == [3, 3] assert normalize(s.diffWaysToCompute("4*2-1")) == [4, 7] print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `"2-1-1"` | Official small example | | `"2*3-4*5"` | Multiple recursive splits | | `"3"` | Base case without operators | | `"1+1+1"` | Duplicate results | | `"4*2-1"` | Mixed operators |