Different Ways to Add Parentheses — Editorial

Opening the reading…

Intuitionwhy every operator is a possible final split

A parenthesized expression has one operation performed last. That last operation must be one of the operators in the expression. If you choose an operator as the final split, everything to its left becomes one complete value, everything to its right becomes another complete value, and the chosen operator combines those two values.

The left and right sides can each have several possible values because they can be parenthesized in several ways. You therefore cannot keep only one answer from either side: every left result must be paired with every right result. The same substring appears in many larger splits, so memoizing its result list prevents the recursion from rebuilding it repeatedly.

Approach

Create a memo map from each substring to its complete list of results, because the same substring can be reached through many different larger parenthesizations.

For a substring, scan every character and treat each operator as a possible final split, because every valid parenthesization has exactly one operator that is performed last.

Recursively compute the result list for the text before the operator and the text after it, because those two sides are independent once this operator is chosen.

Take the Cartesian product of the two lists and apply the chosen operator to each pair, because choosing one left parenthesization and one right parenthesization creates one valid parenthesization of the whole substring.

If the scan found no operator, convert the substring to one integer and return it, because a number has exactly one possible value and otherwise the recursion would leave its result list empty.

Store the completed list in the memo before returning it, because future splits should reuse the list instead of repeating all of its recursive work.

Start the recursion with the entire expression and return its list, because every valid placement of parentheses is represented by one of the possible final splits at the top level.

Complexityoutput-sensitive because the answer itself can be large

MEASURE	BOUND	WHY
Time	O(n^3 + n k)	There are O(n^2) substring states; scanning and constructing substring keys across those states costs O(n^3) in this string-key implementation. The nested combinations generate every stored intermediate result, and the total can be bounded by O(n k), so the bound includes the work needed to produce the output.
Space	O(n^2 + n k) extra	The memo stores O(n^2) substring keys and result vectors whose total size is bounded by O(n k); the recursion stack adds O(n). The returned result list is required output and is excluded, but memoized intermediate lists remain working memory. Inputs with many operators make k, and therefore the space use, exponential in the operator count.

Here n is the length of the input string and k is the number of results for the complete expression. When the expression has many operators, k can grow exponentially with the number of operators.

Annotated solutionC++ · top-down memoized divide-and-conquer

CPPThe memoized recursion evaluates every substring once and combines all left-right result pairs.

#include <functional>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        unordered_map<string, vector<int>> memo;

        function<vector<int>(const string&)> compute = [&](const string& s) {
            auto found = memo.find(s);
            if (found != memo.end()) {
                return found->second;
            }

            vector<int> results;
            for (int i = 0; i < static_cast<int>(s.size()); ++i) {
                char op = s[i];
                if (op != '+' && op != '-' && op != '*') {
                    continue;
                }

                vector<int> left = compute(s.substr(0, i));
                vector<int> right = compute(s.substr(i + 1));

                for (int a : left) {
                    for (int b : right) {
                        if (op == '+') {
                            results.push_back(a + b);
                        } else if (op == '-') {
                            results.push_back(a - b);
                        } else {
                            results.push_back(a * b);
                        }
                    }
                }
            }

            if (results.empty()) {
                results.push_back(stoi(s));
            }

            memo[s] = results;
            return results;
        };

        return compute(expression);
    }
};

The test for an empty results vector is the base case in disguise. A substring with no operator is one number, so it contributes exactly one result. The two nested loops are equally important: they preserve every combination of a left parenthesization and a right parenthesization instead of accidentally selecting only one pairing.

The iterative alternativethe same interval recurrence without recursive calls

You can replace substring memoization with interval dynamic programming. First tokenize the expression into numbers and operators. Then dp[i][j] stores every value obtainable from the consecutive numbers i through j. Intervals of length one contain their number, and longer intervals are built by trying each operator between them. This is a different arrangement, not an asymptotic optimization: it avoids recursive calls and repeated string-key work, but requires explicit tokenization and a two-dimensional table.

CPPBottom-up interval dynamic programming builds result lists from shorter number ranges to longer ones.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> numbers;
        vector<char> operators;

        for (int i = 0; i < static_cast<int>(expression.size()); ) {
            int value = 0;
            while (i < static_cast<int>(expression.size()) &&
                   expression[i] >= '0' && expression[i] <= '9') {
                value = value * 10 + (expression[i] - '0');
                ++i;
            }
            numbers.push_back(value);

            if (i < static_cast<int>(expression.size())) {
                operators.push_back(expression[i]);
                ++i;
            }
        }

        int count = static_cast<int>(numbers.size());
        vector<vector<vector<int>>> dp(
            count, vector<vector<int>>(count));

        for (int i = 0; i < count; ++i) {
            dp[i][i].push_back(numbers[i]);
        }

        for (int length = 2; length <= count; ++length) {
            for (int left = 0; left + length <= count; ++left) {
                int right = left + length - 1;

                for (int split = left; split < right; ++split) {
                    char op = operators[split];
                    for (int a : dp[left][split]) {
                        for (int b : dp[split + 1][right]) {
                            if (op == '+') {
                                dp[left][right].push_back(a + b);
                            } else if (op == '-') {
                                dp[left][right].push_back(a - b);
                            } else {
                                dp[left][right].push_back(a * b);
                            }
                        }
                    }
                }
            }
        }

        return dp[0][count - 1];
    }
};