# 241. Different Ways to Add Parentheses

## problem description

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

## algorithm thought

这里最简答的方法就是回溯法，因为可以随意加括号，有很多不确定性。使用回溯法，在每个能加括号的地方，进行回溯。但是回溯法时间复杂度太高，往往可以用备忘录的方式，消除重复的回溯。所以这里用一个map来保存每次运行后的结果。进入函数的时候，首先检查是否在map中已经保存了，如果保存了，就直接返回。

在函数中，处理方式就是，找到每个操作符，对操作符左右分别进行递归处理。 最后将结果保存在map中即可

## code

```cpp
class Solution {
public:
    unordered_map<string,vector<int>> ma;
    vector<int> diffWaysToCompute(string input) {
        cout<<input<<' ';
        if(ma.count(input))
            return ma[input];
        vector<int> res;
        int now=0;
        for(int i=0;i<input.size();++i){
            if(input[i]=='+'||input[i]=='*'||input[i]=='-'){
                vector<int> left=diffWaysToCompute(input.substr(0,i));
                vector<int> right=diffWaysToCompute(input.substr(i+1));
                for(auto l:left){
                    for(auto r:right){
                        if(input[i]=='+'){
                            res.push_back(l+r);
                        }else if(input[i]=='*'){
                            res.push_back(l*r);
                        }else{
                            res.push_back(l-r);
                        }
                    }
                }
            }
        }
        if(res.size()==0){
            res.push_back(atoi(input.c_str()));
        }
        return ma[input]=res;
    }
};
```

## algorithm analysis

回溯法时间复杂度是O(2^n)的时间复杂度，这里加入了map的方式，会快一点。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/241.-different-ways-to-add-parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.