> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0241-different-ways-to-add-parentheses.md).

# 0241. Different Ways to Add Parentheses

<https://leetcode.com/problems/different-ways-to-add-parentheses>

## Description

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]`.

## ac: divide and conquer

```java
class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();

        List<Integer> l1 = new ArrayList<Integer>();
        List<Integer> l2 = new ArrayList<Integer>();

        for (int i = 0; i < input.length(); i++) {
            // meet operator, divide 2 parts, get result list
            if (input.charAt(i) == '+'
               || input.charAt(i) == '-'
               || input.charAt(i) == '*') {
                l1 = diffWaysToCompute(input.substring(0, i));
                l2 = diffWaysToCompute(input.substring(i+1));

                // conquer 2 result
                for (int i1 : l1) {
                    for (int i2 : l2) {
                        int tmp = 0;
                        switch(input.charAt(i)) {
                            case '+':
                                tmp = i1 + i2;
                                break;
                            case '-':
                                tmp = i1 - i2;
                                break;
                            case '*':
                                tmp = i1 * i2;
                        }
                        res.add(tmp);
                    }
                }
            }
        }

        // do not contain operator, return value
        if (res.size() == 0) res.add(Integer.parseInt(input));

        return res;
    }
}

/**
walk, meet + - *, divide 2 parts, recursion
**/
```