241. Different Ways to Add Parentheses


Problem Description

The problem in question requires us to compute all possible results from a given string expression which includes numbers and arithmetic operators ('+', '-', '*'). The key challenge is to consider all the different groupings of the numbers and operators to find every possible evaluation outcome.

Imagine you have an expression like "2-1-1". If you group the numbers and operators differently, you get different results:

  • ((2-1)-1) = 0
  • (2-(1-1)) = 2

The goal is to find all such distinct values that can be obtained by all the different possible ways to group the numbers and operators. This problem is inherently recursive, as each time you encounter an operator, you have two sub-expressions (left and right) which can themselves be broken down further.

Intuition

The provided solution uses a recursive approach with memoization to solve the problem efficiently. The basic idea is to use recursion to break down the expression at every operator, compute all possible results for the left and right sub-expressions separately, and then combine these results according to the current operator.

Here's a step-by-step breakdown of the solution approach:

  1. Define a recursive function dfs that will compute and return all possible outcomes of a given expression.
  2. Base Case: If the input to dfs is a single number, we return a list containing just that number.
  3. Recursive Case: If the input contains operators, iterate through each character in the expression.
    • When an operator is encountered, split the expression into left and right sub-expressions at that operator.
    • Recursively call dfs on the left and right sub-expressions to compute their results separately.
    • Once we have the results from the left and right sides, combine each pair of results from the left and right using the current operator.
  4. Cache the results for each sub-expression to avoid re-computation (this is done using the @cache decorator). This step makes the solution much faster, as the number of unique sub-expressions is significantly less than the total number of calls made during the recursive process.
  5. Initiate the recursive function with the full expression to get all possible results and return them.

This approach leverages the power of recursion to solve a complex problem by breaking it down into simpler sub-problems, solving each sub-problem once, caching the solution, and combining these solutions to get the final result set.

Solution Approach

The implementation of the solution adopts a divide-and-conquer strategy and utilizes Python's built-in memorization technique using the cache decorator from the functools module. This strategy is laid out in the recursive dfs function. Here is how the solution unfolds:

  1. Memoization: The @cache decorator is used to memoize the dfs function. It helps in storing the results of expensive function calls and returning the cached result when the same inputs occur again. This is essential since many sub-expressions will repeat in the evaluation process and we do not want to recompute them each time.

  2. Recursive Function (dfs): This function is the heart of the solution. It takes as input a sub-expression (exp) of the entire expression and returns all outcomes of this sub-expression as a list of integers.

  3. Base Case: If the exp is solely composed of digits with no operators, we convert it to an integer and return it in a list format. This signifies the end of the recursion for that path, i.e., when we're down to a single numerical value.

    1if exp.isdigit():
    2    return [int(exp)]
  4. Recursive Case: When exp contains operators, we iterate over each character:

    1for i, c in enumerate(exp):
    2    if c in '-+*':
    • For each operator we find (c), we divide the exp into two parts: left of the operator (exp[:i]) and right of the operator (exp[i + 1 :]).

    • We then recursively call dfs on these parts, which gives us all possible outcomes for both left and right sub-expressions.

    1left, right = dfs(exp[:i]), dfs(exp[i + 1 :])
    • After that, we perform calculations based on the type of operator. We run through every combination of results from left and right, performing the operation dictated by c on each pair:
    1for a in left:
    2    for b in right:
    3        if c == '-':
    4            ans.append(a - b)
    5        elif c == '+':
    6            ans.append(a + b)
    7        else:
    8            ans.append(a * b)
    • The results for each sub-expression, after combining with the operator, are stored in a temporary list called ans.
  5. Collecting Results: Once all possible operations on the sub-expressions are complete, ans is returned to the caller. This process continues recursively, gathering results from sub-expressions, combining them, and passing them up the call stack.

  6. Initiate and Return: Finally, dfs is initiated with the full initial expression as the parameter.

    1return dfs(expression)

All the recursive calls to dfs, and the memoization through @cache, ensures that every unique sub-expression is evaluated only once, and the results are reused wherever necessary. This brings down the time complexity significantly, which is important given the statement that the number of results does not exceed 10^4.

By systematically considering every split at each operator and recursively solving smaller problems, the function finally returns a list of all possible results for the initial expression.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through a small example using the solution approach.

Consider the expression "23-45". We want to calculate all possible results from different combinations of parentheses placement.

We begin with the dfs function, which is a recursive function that helps compute all possible outcomes:

  1. The initial call is with the whole expression dfs("2*3-4*5").

  2. The function iterates through the expression character by character. When it encounters operators, it divides the expression and performs recursive calls.

    For example, it first encounters the operator * between "2" and "3". It will then make two recursive calls: dfs("2") for the left sub-expression and dfs("3-4*5") for the right sub-expression.

  3. The dfs("2") is a base case which is a single number and returns [2].

  4. dfs("3-4*5") will further break down into other expressions when it encounters the - and * operators respectively.

  5. This process of breaking down expressions continues until all sub-expressions are single numbers.

  6. During the recursive calls, each dfs will eventually return a list of results.

  7. As the recursion unwinds, the function starts combining the results from left and right sub-expressions with the operators that led to their division. The combine operation follows based on the type of the operator:

    • If the expression was split by a *, the results from the left and right are multiplied.
    • If the split was by a +, the results from each side are added.
    • If the division happened due to a -, the results from the left are subtracted from the results from the right.

For "23-45", the recursive calls will eventually perform operations like:

  • The results of dfs("2") ([2]) will be multiplied with the results of dfs("3") ([3]), yielding 6.
  • Then, dfs("4") ([4]) will be multiplied with dfs("5") ([5]), yielding 20.
  • Ultimately, dfs("3-4*5") will evaluate to [3-20], which equals [-17].
  • Finally, the results of dfs("2") and dfs("3-4*5") will be combined to give the final result as [2*-17], which is [-34].
  1. Since the memoization is enabled with @cache, the results for each sub-expression are stored and reused, saving a significant amount of computation.

  2. By following this method recursively and combining the left and right sub-expression results using the operators, we construct all possible evaluation results.

In this example, dfs would be called like:

1dfs("2*3-4*5") -> combines results from dfs("2") * dfs("3-4*5")
2dfs("3-4*5") ->  combines results from dfs("3") - dfs("4*5")
3dfs("4*5") -> combines results from dfs("4") * dfs("5")
4# And so on for each operator encountered...

When computation finishes, dfs("2*3-4*5") will return a list of all the possible outcomes that can be achieved by adding parentheses in our example expression in different ways. These outcomes will be the complete set of distinct values that can be obtained for the expression "23-45".

Python Solution

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def diff_ways_to_compute(self, expression: str) -> List[int]:
6        # Define a helper function that will find all possible results
7        # of computations given a sub-expression. The lru_cache decorator
8        # is used to memoize the results of the function calls, effectively
9        # caching the intermediate results for optimization.
10        @lru_cache(maxsize=None)
11        def compute_all_ways(sub_exp):
12            # If the sub-expression is a digit, convert it to an integer
13            # and return it as a list.
14            if sub_exp.isdigit():
15                return [int(sub_exp)]
16
17            # Initialize an empty list to store possible computation results.
18            results = []
19
20            # Iterate through each character in the sub-expression.
21            for idx, char in enumerate(sub_exp):
22                # Check if the current character is an operator.
23                if char in '-+*':
24                    # Compute all possible results for the left and right
25                    # sub-expressions.
26                    left_results = compute_all_ways(sub_exp[:idx])
27                    right_results = compute_all_ways(sub_exp[idx + 1:])
28
29                    # Iterate through all combinations of left and
30                    # right results, and apply the operator.
31                    for left_val in left_results:
32                        for right_val in right_results:
33                            # Perform the appropriate operation based
34                            # on the operator.
35                            if char == '-':
36                                results.append(left_val - right_val)
37                            elif char == '+':
38                                results.append(left_val + right_val)
39                            else:  # char == '*'
40                                results.append(left_val * right_val)
41          
42            # Return all possible computation results for this sub-expression.
43            return results
44
45        # Call the helper function on the entire expression to find all
46        # different ways to compute the expression.
47        return compute_all_ways(expression)
48

Java Solution

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6public class Solution {
7  
8    // Cache to store already computed results for expressions.
9    private static Map<String, List<Integer>> memoizationCache = new HashMap<>();
10
11    // This method starts the process by calling the 'computeAllPossibleResults' helper method.
12    public List<Integer> diffWaysToCompute(String expression) {
13        return computeAllPossibleResults(expression);
14    }
15
16    // Recursive function to compute all possible results from the input expression.
17    private List<Integer> computeAllPossibleResults(String expression) {
18        // Check if the result for this expression is cached.
19        if (memoizationCache.containsKey(expression)) {
20            return memoizationCache.get(expression);
21        }
22        List<Integer> results = new ArrayList<>();
23      
24        // Base case: if expression is a single number, return it as the only result.
25        if (!expression.contains("+") && !expression.contains("-") && !expression.contains("*")) {
26            results.add(Integer.parseInt(expression));
27            return results;
28        }
29      
30        // Iterate through each character of the expression string.
31        for (int i = 0; i < expression.length(); i++) {
32            char operation = expression.charAt(i);
33            // When an operator is found, divide the expression into two parts.
34            if (operation == '-' || operation == '+' || operation == '*') {
35                List<Integer> resultsLeft = computeAllPossibleResults(expression.substring(0, i));
36                List<Integer> resultsRight = computeAllPossibleResults(expression.substring(i + 1));
37              
38                // Compute all combinations of results from left and right sub-expressions.
39                for (int leftResult : resultsLeft) {
40                    for (int rightResult : resultsRight) {
41                        if (operation == '-') {
42                            results.add(leftResult - rightResult);
43                        } else if (operation == '+') {
44                            results.add(leftResult + rightResult);
45                        } else if (operation == '*') {
46                            results.add(leftResult * rightResult);
47                        }
48                    }
49                }
50            }
51        }
52      
53        // Cache the computed results for the current expression.
54        memoizationCache.put(expression, results);
55      
56        // Return all the computed results.
57        return results;
58    }
59}
60

C++ Solution

1#include <vector>
2#include <unordered_map>
3#include <string>
4#include <cctype> // for std::isdigit
5
6class Solution {
7public:
8    // Entry point for the solution that calls dfs() method with the input expression.
9    vector<int> diffWaysToCompute(string expression) {
10        return dfs(expression);
11    }
12
13private:
14    // A memoization map to store previously calculated results for subexpressions.
15    unordered_map<string, vector<int>> memo;
16
17    // Recursive function to compute all possible results from the input expression.
18    vector<int> dfs(const string& exp) {
19        // If the result of this subexpression is already computed, return it.
20        if (memo.count(exp)) return memo[exp];
21      
22        vector<int> results;
23      
24        // Check if the expression is a simple number.
25        if(isNumber(exp)) {
26            results.push_back(stoi(exp));
27            return results;
28        }
29      
30        int n = exp.size();
31        // Iterate over each character of the expression.
32        for (int i = 0; i < n; ++i) {
33            char c = exp[i];
34            // Check if the current character is an operator.
35            if (c == '-' || c == '+' || c == '*') {
36                // Recursively solve subexpression to the left of the operator.
37                vector<int> leftResults = dfs(exp.substr(0, i));
38                // Recursively solve subexpression to the right of the operator.
39                vector<int> rightResults = dfs(exp.substr(i + 1));
40              
41                // Combine the results from both subexpressions based on the operator.
42                for (int a : leftResults) {
43                    for (int b : rightResults) {
44                        if (c == '-')
45                            results.push_back(a - b);
46                        else if (c == '+')
47                            results.push_back(a + b);
48                        else // c == '*'
49                            results.push_back(a * b);
50                    }
51                }
52            }
53        }
54      
55        // Store the computed results in the memoization map before returning.
56        memo[exp] = results;
57        return results;
58    }
59
60    // Helper function to determine if a given string is a number.
61    bool isNumber(const string& str) {
62        return !str.empty() && std::all_of(str.begin(), str.end(), ::isdigit);
63    }
64};
65

Typescript Solution

1// Importing necessary utility from TypeScript standard library.
2import { isDigit } from "cctype";
3
4// A memoization map to store previously calculated results for subexpressions.
5const memo: { [key: string]: number[] } = {};
6
7// Entry function that calls the dfs() method with the input expression.
8function diffWaysToCompute(expression: string): number[] {
9    return dfs(expression);
10}
11
12// Recursive function to compute all possible results from the input expression.
13function dfs(exp: string): number[] {
14    // If the result of this subexpression is already computed, return it.
15    if (memo[exp]) {
16        return memo[exp];
17    }
18  
19    const results: number[] = [];
20  
21    // Check if the expression is a simple number.
22    if (isNumber(exp)) {
23        results.push(parseInt(exp));
24        return results;
25    }
26  
27    const n: number = exp.length;
28    // Iterate over each character of the expression.
29    for (let i = 0; i < n; ++i) {
30        const c: string = exp[i];
31        // Check if the current character is an operator.
32        if (c === '-' || c === '+' || c === '*') {
33            // Recursively solve the subexpression to the left of the operator.
34            const leftResults: number[] = dfs(exp.substring(0, i));
35            // Recursively solve the subexpression to the right of the operator.
36            const rightResults: number[] = dfs(exp.substring(i + 1));
37          
38            // Combine the results from both subexpressions based on the operator.
39            for (const a of leftResults) {
40                for (const b of rightResults) {
41                    switch (c) {
42                        case '-':
43                            results.push(a - b);
44                            break;
45                        case '+':
46                            results.push(a + b);
47                            break;
48                        case '*':
49                            results.push(a * b);
50                            break;
51                    }
52                }
53            }
54        }
55    }
56  
57    // Store the computed results in the memoization map before returning.
58    memo[exp] = results;
59    return results;
60}
61
62// Helper function to determine if a given string is a number.
63function isNumber(str: string): boolean {
64    return str.length > 0 && Array.from(str).every(char => isDigit(char));
65}
66

Time and Space Complexity

The given code is a Divide and Conquer algorithm that computes all possible results from a given arithmetic expression with numbers and operators. The memoization via @cache helps avoid repeated computation for the same sub-expressions.

Time Complexity:

  • There are 2n+1 possibilities for sub-expressions from the given expression of length n, where n is the number of operators.
  • Each sub-expression can be split into two parts at each operator, generating a combination of left and right results which can be anywhere from 1 to Catalan(n) (which is an upper bound on the number of unique BSTs that can be formed with n nodes). The Catalan number grows approximately as 4^n / (n^(3/2) sqrt(pi)), which is less than 2^n.
  • Considering the above facts and the memoization, the upper bound on the time complexity is O(n * 2^n * n) = O(n^2 * 2^n) since for each operator we do two recursive calls and combine their results, plus the iteration for combining results that take O(n) time.

Space Complexity:

  • Due to memoization, we are storing the intermediate results for each sub-expression. The space usage would depend on the number of unique sub-expressions, which is at most O(2^n).
  • Recursive calls will use additional stack space, which could be as deep as the number of operators, adding another O(n) factor.

Taking into account the memoization storage and recursive call stack, the space complexity would be O(2^n + n) = O(2^n), since 2^n should dominate for large n.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫