241

241. Different Ways to Add Parentheses

Medium

118661FavoriteShare

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 *.

Example 1:

Input: "2-1-1" Output: [0, 2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2

Example 2:

Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation: (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

 

이 문제는 Divide and Conquer 보다는 살짝 DP 같다 

 

그래도 이해는 됬다. 

 

left right 를 잘라서 더 할때 거기서 더 잘라서 하면 되는거 같다.