Problem editorial

Different Ways to Add Parentheses

MediumDynamic Programming (DP) PatternsMathStringDynamic Programming

Editorial

Core insight

Different Ways to Add Parentheses · Dynamic Programming (DP) Patterns

Core Insight for Different Ways to Add Parentheses

The core insight required to move from brute force to the optimal solution is recognizing that an arithmetic expression is defined by its last operation.

Consider the expression 2 * 3 - 4 * 5. The last operation performed could be:

The first *: The expression is (2) * (3 - 4 * 5)
The -: The expression is (2 * 3) - (4 * 5)
The second *: The expression is (2 * 3 - 4) * (5)

By iterating through the string and treating each operator as the potential "last operation," we effectively partition the problem. The invariant here is that for any substring, the set of possible results is derived solely by splitting that substring at every internal operator and combining the results of the sub-parts.

Visual Description: Imagine the recursion as constructing a tree. The top node represents the full expression 2-1-1.

We pick the first - as the root. The left child is 2 (base case). The right child is 1-1.
The right child 1-1 must be solved. We pick the - inside it. Its children are 1 and 1.
We calculate 1-1 = 0. Now the top node combines 2 and 0 with - to get 2.
Alternatively, the recursion tree branches differently if we pick the second - in the original expression as the root. The left child is 2-1, the right is 1.

Because sub-expressions like 3-4*5 might appear in multiple branches of the recursion tree (if the input were longer), we must cache the results of these substrings to avoid redundant processing.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 241: Different Ways to Add Parentheses Solution & Explanation

Problem Overview

TL;DR: The optimal solution treats every operator as a potential splitting point, recursively computing all possible results for the left and right sub-expressions and combining them via the Cartesian product, using memoization to store results of repeated substrings.

The problem asks us to parse a string containing numbers and operators (+, -, *). We must insert parentheses in every possible valid configuration to determine the order of operations. The goal is to return a list of all possible computed values derived from these different groupings.

This is a classic "Divide and Conquer" problem that overlaps significantly with Dynamic Programming. It is widely known as LeetCode 241: Different Ways to Add Parentheses and is a popular interview question for testing recursion and structural intuition.

Brute Force Approach for Different Ways to Add Parentheses

The brute force approach involves simple recursion without storing intermediate results. For every operator found in the expression, we split the string into two parts: a left operand and a right operand. We recursively call the function on both parts to get two lists of possible results. Finally, we combine every number from the left list with every number from the right list using the current operator.

Pseudo-code:

text

function solve(input):
    results = []
    for i from 0 to length of input:
        if input[i] is operator:
            left_results = solve(input[0...i])
            right_results = solve(input[i+1...end])
            
            for l in left_results:
                for r in right_results:
                    results.add(calculate(l, input[i], r))
    
    if results is empty:
        results.add(integer(input))
        
    return results

Complexity Analysis: The time complexity of this naive approach follows the Catalan number sequence. For an expression with $n$ operators, the number of ways to parenthesize it is the $n$ -th Catalan number, which grows asymptotically as $O(4^n / n^{1.5})$ . Without memoization, many sub-expressions (like the middle section of a long string) are re-evaluated exponentially many times. This leads to severe inefficiency, potentially causing Time Limit Exceeded (TLE) on larger inputs, though the constraints here ( $N \le 20$ ) are small enough that brute force might pass but is not optimal.

Algorithm Strategy: DP - Catalan

We implement this using Top-Down Dynamic Programming (Memoization).

State Definition: We maintain a map (or dictionary) where the key is the string representation of an expression (e.g., "2*3-4"), and the value is the list of all possible integer results derived from that expression.
Recursive Step:
- Iterate through the current string expression from index 0 to N-1.
- When an operator (+, -, *) is encountered at index i:
  - Divide: Split the string into leftPart (0 to i-1) and rightPart (i+1 to N).
  - Conquer: Recursively call the function for leftPart and rightPart. Check the memoization map before computing.
  - Combine: The recursive calls return two lists of integers. Use a nested loop to combine every element from the left list with every element from the right list using the operator at index i. Add these new values to our current results list.
Base Case: If the loop finishes and the results list is empty, it implies the current string contains no operators. It is purely a number. Parse the string into an integer and add it to results.
Memoize: Before returning the results list, store it in the map with the current expression as the key.

Execution Flow

Let's trace 2-1-1:

Call diffWaysToCompute("2-1-1")
Loop finds operator - at index 1.
- Split: Left="2", Right="1-1".
- Recurse Left ("2"): No operators. Returns [2].
- Recurse Right ("1-1"):
  - Loop finds - at index 1.
  - Split: Left="1", Right="1".
  - Recurse Left ("1"): Returns [1].
  - Recurse Right ("1"): Returns [1].
  - Combine: 1 - 1 = 0. Returns [0].
- Combine Top Level: Left [2], Right [0]. Operation -. Result: 2 - 0 = 2. List is [2].
Loop continues, finds operator - at index 3.
- Split: Left="2-1", Right="1".
- Recurse Left ("2-1"):
  - Computes 2 - 1. Returns [1].
- Recurse Right ("1"): Returns [1].
- Combine Top Level: Left [1], Right [1]. Operation -. Result: 1 - 1 = 0. List is now [2, 0].
Return: [2, 0] (Order does not matter).

Proof of Correctness

The correctness relies on the property of binary expression trees. Every valid way to parenthesize an expression corresponds to a unique binary tree where leaves are numbers and internal nodes are operators. The algorithm iterates through every possible operator to serve as the root of the tree. By recursively solving for the left and right subtrees (which covers all possible sub-structures due to the inductive hypothesis) and performing a Cartesian product of the results, we guarantee that every valid tree structure—and thus every valid result—is generated exactly once per unique structure.

Pattern Reuse Notes

The pattern "DP - Catalan Numbers" (splitting a problem at every possible pivot point) is directly applicable to:

LeetCode 96: Unique Binary Search Trees - Instead of combining calculation results, you count the number of valid structures.
LeetCode 95: Unique Binary Search Trees II - Instead of returning integers, you return actual TreeNode objects constructed from left and right subtrees.

The logic for partitioning the problem at index i and combining left and right results is identical across these problems.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 241

cpp

1#include <vector>
2#include <string>
3#include <map>
4
5using namespace std;
6
7class Solution {
8private:
9    // Memoization map to store results of substrings
10    map<string, vector<int>> memo;
11
12public:
13    vector<int> diffWaysToCompute(string expression) {
14        // Return cached result if it exists
15        if (memo.find(expression) != memo.end()) {
16            return memo[expression];
17        }
18
19        vector<int> results;
20
21        // Iterate through the expression to find operators
22        for (int i = 0; i < expression.length(); i++) {
23            char c = expression[i];
24
25            // If character is an operator, split and recurse
26            if (c == '+' || c == '-' || c == '*') {
27                string leftExpr = expression.substr(0, i);
28                string rightExpr = expression.substr(i + 1);
29
30                // Recursive calls
31                vector<int> leftResults = diffWaysToCompute(leftExpr);
32                vector<int> rightResults = diffWaysToCompute(rightExpr);
33
34                // Combine results from left and right parts
35                for (int l : leftResults) {
36                    for (int r : rightResults) {
37                        if (c == '+') {
38                            results.push_back(l + r);
39                        } else if (c == '-') {
40                            results.push_back(l - r);
41                        } else if (c == '*') {
42                            results.push_back(l * r);
43                        }
44                    }
45                }
46            }
47        }
48
49        // Base case: if no operator was found, the expression is just a number
50        if (results.empty()) {
51            results.push_back(stoi(expression));
52        }
53
54        // Cache and return
55        return memo[expression] = results;
56    }
57};

Java Solution for LeetCode 241

java

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6class Solution {
7    // Memoization map
8    private Map<String, List<Integer>> memo = new HashMap<>();
9
10    public List<Integer> diffWaysToCompute(String expression) {
11        // Check cache
12        if (memo.containsKey(expression)) {
13            return memo.get(expression);
14        }
15
16        List<Integer> results = new ArrayList<>();
17
18        for (int i = 0; i < expression.length(); i++) {
19            char c = expression.charAt(i);
20
21            // Identify split point (operator)
22            if (c == '-' || c == '+' || c == '*') {
23                String leftPart = expression.substring(0, i);
24                String rightPart = expression.substring(i + 1);
25
26                // Recursively solve sub-problems
27                List<Integer> leftResults = diffWaysToCompute(leftPart);
28                List<Integer> rightResults = diffWaysToCompute(rightPart);
29
30                // Combine results
31                for (int l : leftResults) {
32                    for (int r : rightResults) {
33                        if (c == '-') {
34                            results.add(l - r);
35                        } else if (c == '+') {
36                            results.add(l + r);
37                        } else if (c == '*') {
38                            results.add(l * r);
39                        }
40                    }
41                }
42            }
43        }
44
45        // Base case: No operator found, parse as integer
46        if (results.isEmpty()) {
47            results.add(Integer.parseInt(expression));
48        }
49
50        // Store in cache
51        memo.put(expression, results);
52        return results;
53    }
54}

Python Solution for LeetCode 241

python

1from typing import List
2
3class Solution:
4    def diffWaysToCompute(self, expression: str) -> List[int]:
5        # Memoization dictionary
6        memo = {}
7
8        def solve(expr):
9            if expr in memo:
10                return memo[expr]
11            
12            results = []
13            
14            for i, char in enumerate(expr):
15                if char in "+-*":
16                    # Split expression at the operator
17                    left_part = expr[:i]
18                    right_part = expr[i+1:]
19                    
20                    # Recursive calls
21                    left_results = solve(left_part)
22                    right_results = solve(right_part)
23                    
24                    # Combine results
25                    for l in left_results:
26                        for r in right_results:
27                            if char == '+':
28                                results.append(l + r)
29                            elif char == '-':
30                                results.append(l - r)
31                            elif char == '*':
32                                results.append(l * r)
33            
34            # Base case: if results is empty, expr is a number
35            if not results:
36                results.append(int(expr))
37            
38            memo[expr] = results
39            return results
40
41        return solve(expression)

AI Coach Insight

For Different Ways to Add Parentheses, focus on explaining why the structure works, not just naming Dynamic Programming (DP) Patterns.

Complexity Analysis

Time Complexity: $O(C_n \cdot K)$ or loosely $O(2^N)$ The number of ways to parenthesize an expression is given by the Catalan number $C_m$ , where $m$ is the number of operators. $C_m \approx \frac{4^m}{m^{3/2}}$ . With memoization, we process each unique substring once. However, the list of results for a substring can be large. In the worst case, the time complexity is dominated by the combination step (Cartesian product). Given the constraints ( $N \le 20$ ), this is well within limits.

Space Complexity: $O(2^N)$ This includes the space for the recursion stack and the memoization table. The memoization table stores a list of results for every substring. The size of these lists can grow exponentially in the worst case, although typically much smaller for simple arithmetic expressions.

Related Patterns

Pattern: Dynamic Programming (DP) Patterns
Subpattern: DP - Catalan Numbers

This problem fits the DP - Catalan Numbers subpattern because the structure of the solution involves iterating through every element (operator) to act as a "root" or "pivot," dividing the problem into independent subproblems (left and right) that share the same structure. This is mathematically identical to counting Unique Binary Search Trees or matrix chain multiplication.

Common Mistakes & FAQ

Why do I get an empty list for single numbers?
- Mistake: Failing to handle the base case where the string contains no operators.
- Reason: The loop looking for operators (+, -, *) will never trigger for a string like "5".
- Consequence: The function returns an empty list instead of [5], causing incorrect calculations upstream.
Why is my solution getting Time Limit Exceeded (TLE)?
- Mistake: Omitting memoization.
- Reason: The recursion tree has many overlapping subproblems. For example, in a long expression, a substring like 3*4-5 might be evaluated multiple times in different branches.
- Consequence: The complexity remains strictly exponential/Catalan without pruning, failing on larger inputs.
Why are my string splits incorrect?
- Mistake: Off-by-one errors in substring or slicing logic.
- Reason: When splitting at index i, the left part is usually 0 to i, and the right part is i+1 to end.
- Consequence: Including the operator in the number parsing step (e.g., parsing *5 as a number) causes runtime exceptions.
Why am I missing some permutations?
- Mistake: Breaking the loop early or not iterating through every operator.
- Reason: Assuming only the first occurrence of an operator matters.
- Consequence: The logic fails to treat every operator as a potential "root" of the expression tree, missing valid groupings.

Practise Different Ways to Add Parentheses and the problems around it

Different Ways to Add Parentheses is a Dynamic Programming (DP) Patterns problem, in the Catalan Numbers subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Different Ways to Add Parentheses · Dynamic Programming (DP) Patterns

Core Insight for Different Ways to Add Parentheses

The core insight required to move from brute force to the optimal solution is recognizing that an arithmetic expression is defined by its last operation.

Consider the expression 2 * 3 - 4 * 5. The last operation performed could be:

The first *: The expression is (2) * (3 - 4 * 5)
The -: The expression is (2 * 3) - (4 * 5)
The second *: The expression is (2 * 3 - 4) * (5)

Visual Description: Imagine the recursion as constructing a tree. The top node represents the full expression 2-1-1.

We pick the first - as the root. The left child is 2 (base case). The right child is 1-1.
The right child 1-1 must be solved. We pick the - inside it. Its children are 1 and 1.
We calculate 1-1 = 0. Now the top node combines 2 and 0 with - to get 2.
Alternatively, the recursion tree branches differently if we pick the second - in the original expression as the root. The left child is 2-1, the right is 1.

Because sub-expressions like 3-4*5 might appear in multiple branches of the recursion tree (if the input were longer), we must cache the results of these substrings to avoid redundant processing.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 241: Different Ways to Add Parentheses Solution & Explanation

Problem Overview

Brute Force Approach for Different Ways to Add Parentheses

Pseudo-code:

text

function solve(input):
    results = []
    for i from 0 to length of input:
        if input[i] is operator:
            left_results = solve(input[0...i])
            right_results = solve(input[i+1...end])
            
            for l in left_results:
                for r in right_results:
                    results.add(calculate(l, input[i], r))
    
    if results is empty:
        results.add(integer(input))
        
    return results

Algorithm Strategy: DP - Catalan

We implement this using Top-Down Dynamic Programming (Memoization).

State Definition: We maintain a map (or dictionary) where the key is the string representation of an expression (e.g., "2*3-4"), and the value is the list of all possible integer results derived from that expression.
Recursive Step:
- Iterate through the current string expression from index 0 to N-1.
- When an operator (+, -, *) is encountered at index i:
  - Divide: Split the string into leftPart (0 to i-1) and rightPart (i+1 to N).
  - Conquer: Recursively call the function for leftPart and rightPart. Check the memoization map before computing.
  - Combine: The recursive calls return two lists of integers. Use a nested loop to combine every element from the left list with every element from the right list using the operator at index i. Add these new values to our current results list.
Base Case: If the loop finishes and the results list is empty, it implies the current string contains no operators. It is purely a number. Parse the string into an integer and add it to results.
Memoize: Before returning the results list, store it in the map with the current expression as the key.

Execution Flow

Let's trace 2-1-1:

Call diffWaysToCompute("2-1-1")
Loop finds operator - at index 1.
- Split: Left="2", Right="1-1".
- Recurse Left ("2"): No operators. Returns [2].
- Recurse Right ("1-1"):
  - Loop finds - at index 1.
  - Split: Left="1", Right="1".
  - Recurse Left ("1"): Returns [1].
  - Recurse Right ("1"): Returns [1].
  - Combine: 1 - 1 = 0. Returns [0].
- Combine Top Level: Left [2], Right [0]. Operation -. Result: 2 - 0 = 2. List is [2].
Loop continues, finds operator - at index 3.
- Split: Left="2-1", Right="1".
- Recurse Left ("2-1"):
  - Computes 2 - 1. Returns [1].
- Recurse Right ("1"): Returns [1].
- Combine Top Level: Left [1], Right [1]. Operation -. Result: 1 - 1 = 0. List is now [2, 0].
Return: [2, 0] (Order does not matter).

Proof of Correctness

Pattern Reuse Notes

The pattern "DP - Catalan Numbers" (splitting a problem at every possible pivot point) is directly applicable to:

LeetCode 96: Unique Binary Search Trees - Instead of combining calculation results, you count the number of valid structures.
LeetCode 95: Unique Binary Search Trees II - Instead of returning integers, you return actual TreeNode objects constructed from left and right subtrees.

The logic for partitioning the problem at index i and combining left and right results is identical across these problems.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 241

cpp

1#include <vector>
2#include <string>
3#include <map>
4
5using namespace std;
6
7class Solution {
8private:
9    // Memoization map to store results of substrings
10    map<string, vector<int>> memo;
11
12public:
13    vector<int> diffWaysToCompute(string expression) {
14        // Return cached result if it exists
15        if (memo.find(expression) != memo.end()) {
16            return memo[expression];
17        }
18
19        vector<int> results;
20
21        // Iterate through the expression to find operators
22        for (int i = 0; i < expression.length(); i++) {
23            char c = expression[i];
24
25            // If character is an operator, split and recurse
26            if (c == '+' || c == '-' || c == '*') {
27                string leftExpr = expression.substr(0, i);
28                string rightExpr = expression.substr(i + 1);
29
30                // Recursive calls
31                vector<int> leftResults = diffWaysToCompute(leftExpr);
32                vector<int> rightResults = diffWaysToCompute(rightExpr);
33
34                // Combine results from left and right parts
35                for (int l : leftResults) {
36                    for (int r : rightResults) {
37                        if (c == '+') {
38                            results.push_back(l + r);
39                        } else if (c == '-') {
40                            results.push_back(l - r);
41                        } else if (c == '*') {
42                            results.push_back(l * r);
43                        }
44                    }
45                }
46            }
47        }
48
49        // Base case: if no operator was found, the expression is just a number
50        if (results.empty()) {
51            results.push_back(stoi(expression));
52        }
53
54        // Cache and return
55        return memo[expression] = results;
56    }
57};

Java Solution for LeetCode 241

java

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6class Solution {
7    // Memoization map
8    private Map<String, List<Integer>> memo = new HashMap<>();
9
10    public List<Integer> diffWaysToCompute(String expression) {
11        // Check cache
12        if (memo.containsKey(expression)) {
13            return memo.get(expression);
14        }
15
16        List<Integer> results = new ArrayList<>();
17
18        for (int i = 0; i < expression.length(); i++) {
19            char c = expression.charAt(i);
20
21            // Identify split point (operator)
22            if (c == '-' || c == '+' || c == '*') {
23                String leftPart = expression.substring(0, i);
24                String rightPart = expression.substring(i + 1);
25
26                // Recursively solve sub-problems
27                List<Integer> leftResults = diffWaysToCompute(leftPart);
28                List<Integer> rightResults = diffWaysToCompute(rightPart);
29
30                // Combine results
31                for (int l : leftResults) {
32                    for (int r : rightResults) {
33                        if (c == '-') {
34                            results.add(l - r);
35                        } else if (c == '+') {
36                            results.add(l + r);
37                        } else if (c == '*') {
38                            results.add(l * r);
39                        }
40                    }
41                }
42            }
43        }
44
45        // Base case: No operator found, parse as integer
46        if (results.isEmpty()) {
47            results.add(Integer.parseInt(expression));
48        }
49
50        // Store in cache
51        memo.put(expression, results);
52        return results;
53    }
54}

Python Solution for LeetCode 241

python

1from typing import List
2
3class Solution:
4    def diffWaysToCompute(self, expression: str) -> List[int]:
5        # Memoization dictionary
6        memo = {}
7
8        def solve(expr):
9            if expr in memo:
10                return memo[expr]
11            
12            results = []
13            
14            for i, char in enumerate(expr):
15                if char in "+-*":
16                    # Split expression at the operator
17                    left_part = expr[:i]
18                    right_part = expr[i+1:]
19                    
20                    # Recursive calls
21                    left_results = solve(left_part)
22                    right_results = solve(right_part)
23                    
24                    # Combine results
25                    for l in left_results:
26                        for r in right_results:
27                            if char == '+':
28                                results.append(l + r)
29                            elif char == '-':
30                                results.append(l - r)
31                            elif char == '*':
32                                results.append(l * r)
33            
34            # Base case: if results is empty, expr is a number
35            if not results:
36                results.append(int(expr))
37            
38            memo[expr] = results
39            return results
40
41        return solve(expression)

Different Ways to Add Parentheses

Core insight

Core Insight for Different Ways to Add Parentheses

Full breakdown

LeetCode 241: Different Ways to Add Parentheses Solution & Explanation

Problem Overview

Brute Force Approach for Different Ways to Add Parentheses

Algorithm Strategy: DP - Catalan

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 241

Java Solution for LeetCode 241

Python Solution for LeetCode 241

Practise Different Ways to Add Parentheses and the problems around it

Related problems

Different Ways to Add Parentheses

Core insight

Core Insight for Different Ways to Add Parentheses

Full breakdown

LeetCode 241: Different Ways to Add Parentheses Solution & Explanation

Problem Overview

Brute Force Approach for Different Ways to Add Parentheses

Algorithm Strategy: DP - Catalan

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 241

Java Solution for LeetCode 241

Python Solution for LeetCode 241

Practise Different Ways to Add Parentheses and the problems around it

Related problems