LeetCode 241: Different Ways to Add Parentheses (Divide & Conquer + Memoization)
LeetCode 241Divide and ConquerMemoizationExpression ParsingToday we solve LeetCode 241 - Different Ways to Add Parentheses.
Source: https://leetcode.com/problems/different-ways-to-add-parentheses/
English
Problem Summary
Given an expression string containing digits and operators +, -, and *, return all possible results from computing all different valid parenthesizations.
Key Insight
Each operator can be treated as the last operation. Split expression into left and right subexpressions around that operator, recursively compute all results from each side, then combine pairwise.
Algorithm (Divide & Conquer + Memo)
1) If substring has no operator, parse it as an integer and return singleton list.
2) For every operator index i in substring:
- recursively get all left values and right values;
- compute cross-product using current operator.
3) Memoize by substring to avoid repeated recomputation.
4) Return collected list.
Complexity Analysis
Let n be expression length. Number of binary partition structures grows Catalan-like, so output size dominates.
With memoization, repeated substring evaluation is cached; practical complexity is roughly proportional to number of unique substrings and produced combinations.
Common Pitfalls
- Forgetting multi-digit numbers (not single chars only).
- Missing memoization and timing out on repeated subexpressions.
- Returning set instead of list (problem allows duplicate results).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
private final Map<String, List<Integer>> memo = new HashMap<>();
public List<Integer> diffWaysToCompute(String expression) {
if (memo.containsKey(expression)) return memo.get(expression);
List<Integer> res = new ArrayList<>();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == '+' || ch == '-' || ch == '*') {
List<Integer> left = diffWaysToCompute(expression.substring(0, i));
List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
for (int a : left) {
for (int b : right) {
if (ch == '+') res.add(a + b);
else if (ch == '-') res.add(a - b);
else res.add(a * b);
}
}
}
}
if (res.isEmpty()) res.add(Integer.parseInt(expression));
memo.put(expression, res);
return res;
}
}func diffWaysToCompute(expression string) []int {
memo := make(map[string][]int)
var dfs func(string) []int
dfs = func(s string) []int {
if v, ok := memo[s]; ok {
return v
}
res := []int{}
for i := 0; i < len(s); i++ {
ch := s[i]
if ch == '+' || ch == '-' || ch == '*' {
left := dfs(s[:i])
right := dfs(s[i+1:])
for _, a := range left {
for _, b := range right {
if ch == '+' {
res = append(res, a+b)
} else if ch == '-' {
res = append(res, a-b)
} else {
res = append(res, a*b)
}
}
}
}
}
if len(res) == 0 {
num := 0
for i := 0; i < len(s); i++ {
num = num*10 + int(s[i]-'0')
}
res = append(res, num)
}
memo[s] = res
return res
}
return dfs(expression)
}class Solution {
unordered_map<string, vector<int>> memo;
public:
vector<int> diffWaysToCompute(string expression) {
if (memo.count(expression)) return memo[expression];
vector<int> res;
for (int i = 0; i < (int)expression.size(); ++i) {
char ch = expression[i];
if (ch == '+' || ch == '-' || ch == '*') {
vector<int> left = diffWaysToCompute(expression.substr(0, i));
vector<int> right = diffWaysToCompute(expression.substr(i + 1));
for (int a : left) {
for (int b : right) {
if (ch == '+') res.push_back(a + b);
else if (ch == '-') res.push_back(a - b);
else res.push_back(a * b);
}
}
}
}
if (res.empty()) res.push_back(stoi(expression));
memo[expression] = res;
return res;
}
};from functools import lru_cache
from typing import List
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
@lru_cache(None)
def dfs(s: str) -> List[int]:
ans = []
for i, ch in enumerate(s):
if ch in '+-*':
left = dfs(s[:i])
right = dfs(s[i + 1:])
for a in left:
for b in right:
if ch == '+':
ans.append(a + b)
elif ch == '-':
ans.append(a - b)
else:
ans.append(a * b)
if not ans:
ans.append(int(s))
return ans
return dfs(expression)var diffWaysToCompute = function(expression) {
const memo = new Map();
const dfs = (s) => {
if (memo.has(s)) return memo.get(s);
const res = [];
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (ch === '+' || ch === '-' || ch === '*') {
const left = dfs(s.slice(0, i));
const right = dfs(s.slice(i + 1));
for (const a of left) {
for (const b of right) {
if (ch === '+') res.push(a + b);
else if (ch === '-') res.push(a - b);
else res.push(a * b);
}
}
}
}
if (res.length === 0) res.push(Number(s));
memo.set(s, res);
return res;
};
return dfs(expression);
};中文
题目概述
给定只包含数字和 +、-、* 的表达式字符串，要求返回所有可能加括号方式对应的计算结果。
核心思路
把每个运算符当作“最后一步运算”。在该位置将表达式拆成左右两段，分别递归求出所有结果，再做笛卡尔积合并。
算法步骤（分治 + 记忆化）
1）若当前子串不含运算符，直接转成整数返回。
2）遍历子串中的每个运算符位置：
- 递归计算左子串结果列表与右子串结果列表；
- 按当前运算符两两组合。
3）用子串作为 key 做记忆化缓存，避免重复计算。
4）返回汇总结果。
复杂度分析
表达式拆分结构数量接近 Catalan 增长，输出规模本身会很大。
使用记忆化后，同一子串仅计算一次，整体成本主要由“不同子串数 + 组合结果数”决定。
常见陷阱
- 忽略多位数解析（不是逐字符数字）。
- 不做缓存导致大量重复递归。
- 使用去重集合导致合法重复结果丢失。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
private final Map<String, List<Integer>> memo = new HashMap<>();
public List<Integer> diffWaysToCompute(String expression) {
if (memo.containsKey(expression)) return memo.get(expression);
List<Integer> res = new ArrayList<>();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == '+' || ch == '-' || ch == '*') {
List<Integer> left = diffWaysToCompute(expression.substring(0, i));
List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
for (int a : left) {
for (int b : right) {
if (ch == '+') res.add(a + b);
else if (ch == '-') res.add(a - b);
else res.add(a * b);
}
}
}
}
if (res.isEmpty()) res.add(Integer.parseInt(expression));
memo.put(expression, res);
return res;
}
}func diffWaysToCompute(expression string) []int {
memo := make(map[string][]int)
var dfs func(string) []int
dfs = func(s string) []int {
if v, ok := memo[s]; ok {
return v
}
res := []int{}
for i := 0; i < len(s); i++ {
ch := s[i]
if ch == '+' || ch == '-' || ch == '*' {
left := dfs(s[:i])
right := dfs(s[i+1:])
for _, a := range left {
for _, b := range right {
if ch == '+' {
res = append(res, a+b)
} else if ch == '-' {
res = append(res, a-b)
} else {
res = append(res, a*b)
}
}
}
}
}
if len(res) == 0 {
num := 0
for i := 0; i < len(s); i++ {
num = num*10 + int(s[i]-'0')
}
res = append(res, num)
}
memo[s] = res
return res
}
return dfs(expression)
}class Solution {
unordered_map<string, vector<int>> memo;
public:
vector<int> diffWaysToCompute(string expression) {
if (memo.count(expression)) return memo[expression];
vector<int> res;
for (int i = 0; i < (int)expression.size(); ++i) {
char ch = expression[i];
if (ch == '+' || ch == '-' || ch == '*') {
vector<int> left = diffWaysToCompute(expression.substr(0, i));
vector<int> right = diffWaysToCompute(expression.substr(i + 1));
for (int a : left) {
for (int b : right) {
if (ch == '+') res.push_back(a + b);
else if (ch == '-') res.push_back(a - b);
else res.push_back(a * b);
}
}
}
}
if (res.empty()) res.push_back(stoi(expression));
memo[expression] = res;
return res;
}
};from functools import lru_cache
from typing import List
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
@lru_cache(None)
def dfs(s: str) -> List[int]:
ans = []
for i, ch in enumerate(s):
if ch in '+-*':
left = dfs(s[:i])
right = dfs(s[i + 1:])
for a in left:
for b in right:
if ch == '+':
ans.append(a + b)
elif ch == '-':
ans.append(a - b)
else:
ans.append(a * b)
if not ans:
ans.append(int(s))
return ans
return dfs(expression)var diffWaysToCompute = function(expression) {
const memo = new Map();
const dfs = (s) => {
if (memo.has(s)) return memo.get(s);
const res = [];
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (ch === '+' || ch === '-' || ch === '*') {
const left = dfs(s.slice(0, i));
const right = dfs(s.slice(i + 1));
for (const a of left) {
for (const b of right) {
if (ch === '+') res.push(a + b);
else if (ch === '-') res.push(a - b);
else res.push(a * b);
}
}
}
}
if (res.length === 0) res.push(Number(s));
memo.set(s, res);
return res;
};
return dfs(expression);
};
Comments