Different Ways to Add Parentheses

Medium
1272.

Different Ways to Add Parentheses

Different Ways to Add Parentheses is a medium coding problem on strings, math and recursion, asked in Amazon, Google and Bloomberg interviews.

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 <= 20
  • expression 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 zeros
  • Every intermediate and final value fits in a 32-bit signed integer
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} expression
 * @return {number[]}
 */
var diffWaysToCompute = function(expression) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 20
  • expression 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 zeros
  • Every intermediate and final value fits in a 32-bit signed integer

Hints for Different Ways to Add Parentheses

  1. Hint 1

    Every full parenthesisation has a last operator applied — the root of the tree. Try each operator as the root.

  2. Hint 2

    If the root is the operator at index i, the left side can be any value of expression[..i) and the right side any value of expression(i..]. Combine every pair.

  3. 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

  1. Define ways(lo, hi) = list of values of expression[lo..hi) over all groupings.
  2. For each operator at index i in the range, combine every a in ways(lo, i) with every b in ways(i + 1, hi) using that operator, and append the result.
  3. If the range holds no operator, it is a number: return a list with just its value.
  4. Memoise ways on (lo, hi), call ways(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.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Recursion