# 282. Expression Add Operators

## problem description

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or \* between the digits so they evaluate to the target value.

**Example 1:**

```
Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]
```

**Example 2:**

```
Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
```

**Example 3:**

```
Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
```

**Example 4:**

```
Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]
```

**Example 5:**

```
Input: num = "3456237490", target = 9191
Output: []
```

## algorithm thought

对于每个能放置操作符的地方，有4种情况。第一种是不放置，然后三种是放置3个不同的操作符。

将情况大概讲出来之后，就知道这里使用回溯法解决问题了。这里问题关键在于如果前面是一个加法，然后碰到一个乘法，如何解决。

这里在回溯的时候，保存前面一个操作的数字值。如果当前是乘法，就将当前值减去或者加上前面的值（相当于回溯到前面），然后将前面的值和当前数字相乘，再让前面值加上或者减去当前值。这是大概的思路。实际实现时候，可以优化。

需要注意的是，如果碰到开头为0的字符串需要处理。这里对要求对c++数字和字符串转化操作熟悉

## code

```cpp
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        string now="";
        help(res,target,num,0,0,now,0);
        return res;
    }
    void help(vector<string>&res,int target,string&num,long pre_value,long value,string&now,int pos){
        if(pos==num.size()&&value==target){
            res.push_back(now);
            return;
        }
        for(int i=pos;i<num.size();++i){
            string t=num.substr(pos,i-pos+1);
            if(t.size()>1&&t[0]=='0')
                continue;
            long va=stol(t);

            if(pos==0){
                help(res,target,num,va,va,t,i+1);
                continue;
            }

            int sz=now.size();
            now.push_back('+');now+=t;
            help(res,target,num,va,value+va,now,i+1);
            now[now.size()-t.size()-1]='-';
            help(res,target,num,-va,value-va,now,i+1);
            now[now.size()-t.size()-1]='*';
            help(res,target,num,pre_value*va,value-pre_value+pre_value*va,now,i+1);
            now.resize(sz);
        }
    }
};
```

## algorithm analysis

回溯法时间复杂度分析比较困难，只需要知道这里是指数级时间复杂度。这里还有一个关键的优化在于对string的处理。我看别的答案直接使用operator +，并且没有使用左值引用减少析构和构造。时间复杂度400ms左右。在利用引用优化和+=优化之后，时间复杂度减低到了70ms左右。这么看来string的析构和构造还真挺耗时间的。


---

# 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/282.-expression-add-operators.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.