Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Input: "2-1-1".
((2-1)-1) = 0 (2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
思路：分治。
每个递归这么写：
1. 找到当前字符串的一个符号就分治，left保留符号左边的字符串所能产生的算术值，right保留符号右边所能产生的算术值，再根据符号运算left.size()*right.size()次，得到当前字符串所能产生的所有值，返回结果。
2. 没有找到符号，意味着当前字符串是数值，转换为数值即可。
代码：
1 class Solution { 2 public: 3 vector<int> diffWaysToCompute(string input) {//返回包含当前字符串input所能产生的所有值的vector 4 vector<int> left,right,res; 5 for(int i=0;i<input.size();i++){ 6 if(input[i]==‘+‘||input[i]==‘-‘||input[i]==‘*‘){ 7 left=diffWaysToCompute(input.substr(0,i)); 8 right=diffWaysToCompute(input.substr(i+1)); 9 if(input[i]==‘+‘){ 10 for(auto lnum:left){ 11 for(auto rnum:right){ 12 res.push_back(lnum+rnum); 13 } 14 } 15 continue; 16 } 17 if(input[i]==‘-‘){ 18 for(auto lnum:left){ 19 for(auto rnum:right){ 20 res.push_back(lnum-rnum); 21 } 22 } 23 continue; 24 } 25 if(input[i]==‘*‘){ 26 for(auto lnum:left){ 27 for(auto rnum:right){ 28 res.push_back(lnum*rnum); 29 } 30 } 31 continue; 32 } 33 } 34 } 35 if(!res.size()){ 36 int num=0; 37 for(int i=0;i<input.size();i++){ 38 num*=10; 39 num+=input[i]-‘0‘; 40 } 41 res.push_back(num); 42 } 43 return res; 44 } 45 };
Leetcode 241. Different Ways to Add Parentheses
原文：http://www.cnblogs.com/Deribs4/p/5759732.html