题目：点击打开链接https://leetcode.com/problems/different-ways-to-add-parentheses/?tab=Description
给出一个表达式，求出所有可能的表达式的结果。
（1）对于加括号这个问题，是按照操作符分割来加的。所以每一次都是若干个分治过程，个数等于操作符数目。return case是没有操作符。这个有重叠子问题的特征，因此如果想要降低复杂度，那么可以加一个memo，这里就不加了。这里主要是若干个分治的类型没有见过，需要注意下。通常都是前半部分不需要递归，后半部分需要。
（2）如何计算？这也是一个问题，通常会想到先求出所有的表达式，再依次计算，但是这里可以在每一次加完括号后直接计算，这个思路明显更好。
代码：
public List<Integer> diffWaysToCompute(String input) { if(input == null || input.length() == 0) return new ArrayList<>(); return diffWaysToComputeSub(input, 0, input.length() - 1); } public List<Integer> diffWaysToComputeSub(String input, int start, int end){ List<Integer> r = new ArrayList<>(); for(int i = start; i <= end; i++){ if(input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*'){ List<Integer> front = diffWaysToComputeSub(input, start, i - 1); List<Integer> back = diffWaysToComputeSub(input, i + 1, end); for(int f : front){ for(int b : back){ if(input.charAt(i) == '+') r.add(f + b); else if(input.charAt(i) == '-') r.add(f - b); else r.add(f * b); } } } } if(r.size() == 0) r.add(Integer.parseInt(input.substring(start, end + 1))); return r; }