Different Ways to Add Parentheses

medium math string dp recursion memoization

Problem

Given an expression of digits and the operators +, -, *, return all possible results from computing all the different ways to group numbers and operators. The answer can be in any order.

Inputexpression = "2-1-1"

Output[0, 2]

((2-1)-1)=0 and (2-(1-1))=2.

expression

def diff_ways(expr):
    memo = {}
    def solve(s):
        if s in memo: return memo[s]
        out = []
        for i, c in enumerate(s):
            if c in "+-*":
                for a in solve(s[:i]):
                    for b in solve(s[i+1:]):
                        out.append(a+b if c=='+' else a-b if c=='-' else a*b)
        if not out: out.append(int(s))
        memo[s] = out
        return out
    return solve(expr)

function diffWays(expr) {
  const memo = new Map();
  function solve(s) {
    if (memo.has(s)) return memo.get(s);
    const out = [];
    for (let i = 0; i < s.length; i++) {
      const c = s[i];
      if (c === '+' || c === '-' || c === '*') {
        for (const a of solve(s.slice(0, i)))
          for (const b of solve(s.slice(i + 1)))
            out.push(c === '+' ? a + b : c === '-' ? a - b : a * b);
      }
    }
    if (out.length === 0) out.push(parseInt(s, 10));
    memo.set(s, out);
    return out;
  }
  return solve(expr);
}

class Solution {
    Map<String, List<Integer>> memo = new HashMap<>();
    public List<Integer> diffWaysToCompute(String s) {
        if (memo.containsKey(s)) return memo.get(s);
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                for (int a : diffWaysToCompute(s.substring(0, i)))
                    for (int b : diffWaysToCompute(s.substring(i + 1)))
                        out.add(c == '+' ? a + b : c == '-' ? a - b : a * b);
            }
        }
        if (out.isEmpty()) out.add(Integer.parseInt(s));
        memo.put(s, out);
        return out;
    }
}

unordered_map<string, vector<int>> memo;
vector<int> diffWaysToCompute(string s) {
    if (memo.count(s)) return memo[s];
    vector<int> out;
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (c == '+' || c == '-' || c == '*') {
            for (int a : diffWaysToCompute(s.substr(0, i)))
                for (int b : diffWaysToCompute(s.substr(i + 1)))
                    out.push_back(c=='+'? a+b : c=='-'? a-b : a*b);
        }
    }
    if (out.empty()) out.push_back(stoi(s));
    return memo[s] = out;
}

Explanation

The key idea is divide and conquer: every operator in the expression can be the last operation performed. So we try putting the final parentheses around each operator and combine the results from the two sides.

The solve(s) function scans the string. Whenever it hits an operator c, it recursively computes every possible value of the left part s[:i] and every possible value of the right part s[i+1:]. Then for each pair (a, b) it applies c and collects the result.

If the string has no operator (it is just a number), that is the base case: we simply return [int(s)]. This stops the recursion.

A memo dictionary caches the answer for each substring, so repeated subproblems are computed only once. This avoids the explosion that pure recursion would cause.

Example: "2-1-1". Splitting at the first - gives 2 - (1-1) = 2. Splitting at the second - gives (2-1) - 1 = 0. Collecting both yields [2, 0].

Time: O(C(n) · n) Catalan growth, memoized to polynomial in distinct substrings Space: O(n² · k)