241. Different Ways to Add Parentheses
## 思路
Divide & Conquer
遇到 +,-,* 時
拆成左右兩邊做recursion再作運算
長度<3的就直接轉成數字
1+2*3-4
(1) + (2*3-4) = [1] + [(2*3)-4, 2*(3-4)]
(1+2) * (3-4) = [3] * [-1]
(1+2*3) - (4) = [(1+2)*3, 1+(2*3)] - [4]
## Code
```python
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
@cache
def recur(left, right):
if right - left + 1 < 3:
return [int(expression[left:right+1])]
res = []
for i in range(left, right):
if expression[i] not in {'+', '-', '*'}:
continue
for op1 in recur(left, i-1):
for op2 in recur(i+1, right):
if expression[i] == '+':
res.append(op1 + op2)
elif expression[i] == '-':
res.append(op1 - op2)
else:
res.append(op1 * op2)
return res
return recur(0, len(expression)-1)
```