Get started

Different Ways to Add Parentheses — Medium Problem & Solution

expression is a string of non-negative integers joined by the operators +, - and *, with no spaces and no parentheses.

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

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)))

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 424 strings problems · the whole catalogue

Learn the technique: Strings · Recursion