原题链接在这里：https://leetcode.com/problems/different-ways-to-add-parentheses/
每当遇到运算符时，递归求运算符左侧的string 得到的list, 和 右侧string 得到的list, 然后根据运算符做运算，挨个放到res中。
设a为操作数，~为操作符，对于表达式:
a~a，解空间只有 a ~ a
a~a~a 解空间为 (a~a)~a 和 a~(a~a)
a~a~a~a 解空间为 a~(解空间(a~a~a))和 (解空间(a~a~a))~a
...
因此，要求一个表达式的解空间，可以采用分治策略。例如对于2*3-4*5表达式：
解空间为：
2*解空间（3-4*5）
解空间（2*3） - 解空间（4*5）
解空间（2*3-4）* 解空间（5）
然后在对每个子解空间进行递归求解。
Note: 若是input只有一个数字时，res是空的，此时要特殊处理。
AC Java:
public class Solution { public List<Integer> diffWaysToCompute(String input) { List<Integer> res = new ArrayList<Integer>(); if(input == null || input.length() == 0){ return res; } //扫一遍string, 若现在char是运算符，就把左右两边的结果list 挨个做运算放到res中 for(int i = 0; i<input.length(); i++){ char c = input.charAt(i); if(c == ‘*‘ || c == ‘-‘ || c == ‘+‘){ List<Integer> left = diffWaysToCompute(input.substring(0,i)); List<Integer> right = diffWaysToCompute(input.substring(i+1, input.length())); for(int l:left){ for(int r:right){ int temp = 0; switch(c){ case ‘+‘: temp = l+r; break; case ‘-‘: temp = l-r; break; case ‘*‘: temp = l*r; break; } res.add(temp); } } } } if(res.size() == 0){ res.add(Integer.valueOf(input)); } return res; } }
LeetCode Different Ways to Add Parentheses
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4919244.html