# 241. Different Ways to Add Parentheses

[Leetcode](https://leetcode.com/problems/different-ways-to-add-parentheses/)

Given a string `expression` of numbers and operators, return *all possible results from computing all the different possible ways to group numbers and operators*. You may return the answer in **any order**.

**Example 1:**

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

**Example 2:**

```
Input: expression = "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
```

**Constraints:**

* `1 <= expression.length <= 20`
* `expression` consists of digits and the operator `'+'`, `'-'`, and `'*'`.
* All the integer values in the input expression are in the range `[0, 99]`.

### Basic Idea:

因为可以任意加括号，事实上在计算的时候我们不需要关心四则运算的优先顺序。所谓随便加括号，我们可以使用分治的思路，使用DFS来做。每层我们考虑给定左右边界内的部分，选择一个中间的分界线(一个符号)，递归求分界线两边的所有可能的值，然后对于左右两边的值两两计算分界线处的符号。整个时间复杂度大概是位于 `O(2^n)` ，因为这是所有可能加括号的位置的可能性，但由于括号总是成对出现，实际上的时间复杂度略有出入。

### Java Code:

```java
class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Character> ops = new ArrayList<>();
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < expression.length(); ++i) {
            char c = expression.charAt(i);
            if (!isDigit(c)) {
                ops.add(c);
            } else {
                int num = 0;
                int j = i;
                while (j < expression.length()) {
                    char cj = expression.charAt(j);
                    if (isDigit(cj)) {
                        num = num * 10 + cj - '0';
                        if (j == expression.length() - 1) {
                            numbers.add(num);
                            j++;
                        }
                    } else {
                        numbers.add(num);
                        break;
                    }
                    j++;
                }
                i = j - 1;
            }
        }
        if (ops.isEmpty()) {
            return numbers;
        }
        return dfs(ops, numbers, 0, numbers.size() - 1);
    }
    
    private List<Integer> dfs(List<Character> ops, List<Integer> numbers, int left, int right) {
        if (left == right) {
            return Arrays.asList(numbers.get(left));
        }
        List<Integer> ret = new ArrayList<>();
        for (int i = left; i < right; ++i) {
            char op = ops.get(i);
            List<Integer> leftResList = dfs(ops, numbers, left, i);
            List<Integer> rightResList = dfs(ops, numbers, i + 1, right);
            for (int leftRes : leftResList) {
                for (int rightRes : rightResList) {
                    ret.add(eval(op, leftRes, rightRes));
                }
            }
        }
        return ret;
    }
    
    private int eval(char op, int a, int b) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        if (op == '*') return a * b;
        if (op == '/') return a / b;
        else return Integer.MAX_VALUE;
    }
    
    private boolean isDigit(char c) {
        return '0' <= c && c <= '9';
    }
}
```
