Different Ways to Add Parentheses — Problem & Solution
Different Ways to Add Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Different Ways to Add Parentheses is a medium coding problem on strings, math and recursion, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Medium
- Topics: Strings, Math, Recursion, Memoization
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
expression is a string of non-negative integers joined by the operators +, - and *, with no spaces and no parentheses.
Consider every way to fully parenthesise the expression (every binary tree whose leaves are the numbers in order and whose internal nodes are the operators), and evaluate each one.
Return all the results sorted in ascending order. Different groupings that happen to give the same value are listed separately, so the list has one entry per grouping.
Example 1
Input: expression = "3*4-2"
Output: [6,10]
Explanation: `(3*4)-2 = 10` and `3*(4-2) = 6`.
Example 2
Input: expression = "10-5-2"
Output: [3,7]
Example 3
Input: expression = "1+2*3-4"
Output: [-3,-1,3,3,5]
Explanation: Two different groupings both give 3.
Constraints
1 <= expression.length <= 20expression consists of digits and the operators '+', '-' and '*'All the integer values in the input expression are in the range [0, 99] and have no leading zerosEvery intermediate and final value fits in a 32-bit signed integer
Hints for Different Ways to Add Parentheses
Hint 1
Every full parenthesisation has a last operator applied — the root of the tree. Try each operator as the root.
Hint 2
If the root is the operator at index
i, the left side can be any value ofexpression[..i)and the right side any value ofexpression(i..]. Combine every pair.Hint 3
Recurse on the two sides; an expression with no operator is just a number. Cache results per substring (
lo,hi) so shared sub-expressions are solved once, and sort at the end.
How to solve Different Ways to Add Parentheses
Divide and conquer on the operator applied last: the results for a range are all combinations of the results for its left and right parts, for every operator that could be the root.
Approach
- Define
ways(lo, hi)= list of values ofexpression[lo..hi)over all groupings. - For each operator at index
iin the range, combine everyainways(lo, i)with everybinways(i + 1, hi)using that operator, and append the result. - If the range holds no operator, it is a number: return a list with just its value.
- Memoise
wayson(lo, hi), callways(0, n)and sort the list.
Why it works
A full parenthesisation is a binary tree, and its root is exactly one of the operators; the subtrees are independent full parenthesisations of the left and right parts. So the multiset of values for the range is the union over root operators of the pairwise combinations — which is what the recursion builds, one entry per tree.
Complexity
- Time —
O(C_k · k) results for k operators (C_k is the k-th Catalan number); the memo removes repeated sub-ranges - Space —
O(C_k) for the output and memo
Pitfalls
- Numbers can have two digits — parse the whole number when a range has no operator.
- Do not deduplicate: two groupings with the same value both appear.
- Splitting on the first operator only, or evaluating left to right, misses most groupings.
Reference solution
Python
from typing import List
def diffWaysToCompute(expression: str) -> List[int]:
memo = {}
def ways(lo, hi):
key = lo * 64 + hi
if key in memo:
return memo[key]
out = []
for i in range(lo, hi):
c = expression[i]
if c in "+-*":
left = ways(lo, i)
right = ways(i + 1, hi)
for a in left:
for b in right:
if c == "+":
out.append(a + b)
elif c == "-":
out.append(a - b)
else:
out.append(a * b)
if not out:
out.append(int(expression[lo:hi]))
memo[key] = out
return out
return sorted(ways(0, len(expression)))Java
static List<Integer> dwWays(String e, int lo, int hi, Map<Integer, List<Integer>> memo) {
int key = lo * 64 + hi;
List<Integer> hit = memo.get(key);
if (hit != null) return hit;
List<Integer> out = new ArrayList<>();
for (int i = lo; i < hi; i++) {
char c = e.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = dwWays(e, lo, i, memo), right = dwWays(e, i + 1, hi, memo);
for (int a : left) {
for (int b : right) out.add(c == '+' ? a + b : c == '-' ? a - b : a * b);
}
}
}
if (out.isEmpty()) out.add(Integer.parseInt(e.substring(lo, hi)));
memo.put(key, out);
return out;
}
public static int[] diffWaysToCompute(String expression) {
List<Integer> all = dwWays(expression, 0, expression.length(), new HashMap<>());
int[] res = new int[all.size()];
for (int i = 0; i < res.length; i++) res[i] = all.get(i);
Arrays.sort(res);
return res;
}C++
static vector<int> dwWays(const string& e, int lo, int hi, map<int, vector<int>>& memo) {
int key = lo * 64 + hi;
auto it = memo.find(key);
if (it != memo.end()) return it->second;
vector<int> out;
for (int i = lo; i < hi; i++) {
char c = e[i];
if (c == '+' || c == '-' || c == '*') {
vector<int> left = dwWays(e, lo, i, memo), right = dwWays(e, i + 1, hi, memo);
for (int a : left) {
for (int b : right) out.push_back(c == '+' ? a + b : c == '-' ? a - b : a * b);
}
}
}
if (out.empty()) out.push_back(stoi(e.substr(lo, hi - lo)));
memo[key] = out;
return out;
}
vector<int> diffWaysToCompute(string expression) {
map<int, vector<int>> memo;
vector<int> res = dwWays(expression, 0, expression.size(), memo);
sort(res.begin(), res.end());
return res;
}JavaScript
var diffWaysToCompute = function(expression) {
var memo = new Map();
var ways = function(lo, hi) {
var key = lo * 64 + hi;
if (memo.has(key)) return memo.get(key);
var out = [];
for (var i = lo; i < hi; i++) {
var c = expression[i];
if (c === "+" || c === "-" || c === "*") {
var left = ways(lo, i), right = ways(i + 1, hi);
for (var a = 0; a < left.length; a++) {
for (var b = 0; b < right.length; b++) {
out.push(c === "+" ? left[a] + right[b] : c === "-" ? left[a] - right[b] : left[a] * right[b]);
}
}
}
}
if (out.length === 0) out.push(parseInt(expression.substring(lo, hi), 10));
memo.set(key, out);
return out;
};
return ways(0, expression.length).slice().sort(function(x, y) { return x - y; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.