题目地址：

https://www.lintcode.com/problem/different-ways-to-add-parentheses/description

给定一个中缀表达式，可以将其中加入括号。返回所有可能得到的结果。

思路是记忆化搜索。参考https://blog.csdn.net/qq_46105170/article/details/109441496。代码如下：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    /**
     * @param input: a string
     * @return: return List[int]
     */
    public List<Integer> diffWaysToCompute(String input) {
        // write your code here
        return dfs(input, new HashMap<>());
    }
    
    private List<Integer> dfs(String input, Map<String, List<Integer>> map) {
        if (map.containsKey(input)) {
            return map.get(input);
        }
    
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            if (!Character.isDigit(input.charAt(i))) {
                List<Integer> left = dfs(input.substring(0, i), map), right = dfs(input.substring(i + 1), map);
                for (int l : left) {
                    for (int r : right) {
                        switch (input.charAt(i)) {
                            case '+': res.add(l + r); break;
                            case '-': res.add(l - r); break;
                            case '*': res.add(l * r); break;
                            case '/': res.add(l / r); break;
                        }
                    }
                }
            }
        }
        
        // 这里处理的是base case，即整个input自己就是一个数
        if (res.isEmpty()) {
            res.add(Integer.parseInt(input));
        }
        
        // 做记忆
        map.putIfAbsent(input, res);
        return res;
    }
}

时间复杂度与Catalan数有关，是 O ( C n ) O(C_n) O(Cn​)，空间也是 O ( C n ) O(C_n) O(Cn​)。每个结果对应于一个所有节点组成complete binary tree的方案数。而每棵子树都做了记忆化，所以只会算一次。