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:
- Define a recursive function
dfs
that will compute and return all possible outcomes of a given expression. - Base Case: If the input to
dfs
is a single number, we return a list containing just that number. - 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.
- 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. - 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.
Learn more about Recursion, Memoization, Math and Dynamic Programming patterns.
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:
-
Memoization: The
@cache
decorator is used to memoize thedfs
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. -
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. -
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)]
-
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 theexp
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
andright
, performing the operation dictated byc
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
.
-
-
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. -
Initiate and Return: Finally,
dfs
is initiated with the full initialexpression
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
The initial call is with the whole expression
dfs("2*3-4*5")
. -
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 anddfs("3-4*5")
for the right sub-expression. -
The
dfs("2")
is a base case which is a single number and returns[2]
. -
dfs("3-4*5")
will further break down into other expressions when it encounters the-
and*
operators respectively. -
This process of breaking down expressions continues until all sub-expressions are single numbers.
-
During the recursive calls, each
dfs
will eventually return a list of results. -
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.
- If the expression was split by a
For "23-45", the recursive calls will eventually perform operations like:
- The results of
dfs("2")
([2]) will be multiplied with the results ofdfs("3")
([3]), yielding 6. - Then,
dfs("4")
([4]) will be multiplied withdfs("5")
([5]), yielding 20. - Ultimately,
dfs("3-4*5")
will evaluate to[3-20]
, which equals [-17]. - Finally, the results of
dfs("2")
anddfs("3-4*5")
will be combined to give the final result as[2*-17]
, which is [-34].
-
Since the memoization is enabled with
@cache
, the results for each sub-expression are stored and reused, saving a significant amount of computation. -
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".
Solution Implementation
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
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
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
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 lengthn
, wheren
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 withn
nodes). The Catalan number grows approximately as4^n / (n^(3/2) sqrt(pi))
, which is less than2^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 takeO(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
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.