⚡Flashcard Drill➔
NeetCode #510LC-241MediumBacktracking
← Back to All Problems

#510 · #241 · Different Ways to Add Parentheses(为运算表达式设计优先级)

📌 Problem Statement & Constraints

Given a string expression of numbers and the operators +, -, *, return all possible results from computing all the different ways to parenthesise the expression. Constraints: 1 <= expression.length <= 20; the expression consists of digits and operators; numbers have no leading zeros.

💡 Core Algorithmic Approaches

  1. Divide and conquer on the operators: for each operator, split into a left and a right sub-expression and combine every pair of results.
  2. A sub-expression with no operator is a single number.
  3. Memoise the results per sub-expression string (or per index range) to avoid recomputing shared subproblems.
  4. The number of results is the Catalan number, so the output itself is exponential.

💻 Benchmark Python3 Implementation

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        memo = {}

        def dfs(expr: str) -> List[int]:
            if expr in memo:
                return memo[expr]
            res = []
            for i, ch in enumerate(expr):
                if ch in "+-*":            # split at this operator
                    for l in dfs(expr[:i]):
                        for r in dfs(expr[i + 1:]):
                            if ch == "+":
                                res.append(l + r)
                            elif ch == "-":
                                res.append(l - r)
                            else:
                                res.append(l * r)
            if not res:
                res.append(int(expr))      # a pure number
            memo[expr] = res
            return res

        return dfs(expression)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(Catalan(n) * n) where n is the number of operators.
💾 Space Complexity
O(Catalan(n) * n) for the memo table.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the pure-number base case: an expression with no operator must yield its own value.
  • Not memoising: the same sub-expression would be recomputed exponentially many times.
  • Splitting on digits instead of operators: the split points are exactly the operator positions.
  • Trying to handle multi-digit numbers by splitting on characters: the substring slicing handles them naturally.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems