# Expression Add Operators

> 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.
>
> Examples:
>
> "123", 6 -> \["1+2+3", "1\*2\*3"]
>
> "232", 8 -> \["2\*3+2", "2+3\*2"]
>
> "105", 5 -> \["1\*0+5","10-5"]
>
> "00", 0 -> \["0+0", "0-0", "0\*0"]
>
> "3456237490", 9191 -> \[]

## Thoughts

给一个由数字构成的字符串，往其中添加+-\*/号使得最后eval等于target，返回所有可能的添加方法。all combination想dfs。 由于乘法具有最高优先级, 因此要把上个合理的乘法因子存下来。 而且根据题意中间数字如果是"06"应该跳过。

## Code

```cpp
class Solution {
public:
    void dfs(string &s, const int target, const int pos, const long cur, const long last, string path, vector<string> &res) {
        if (pos == s.size()) {
            if (cur == target) res.push_back(path);
            return;
        }

        for (int i = pos; i < s.size(); ++i) {
            if (pos != i && s[pos] == '0') break;
            const auto snum = s.substr(pos, i - pos + 1);
            const auto num = stol(snum);
            if (pos == 0) {
                dfs(s, target, i + 1, cur + num, num, snum, res);
                continue;
            }
            dfs(s, target, i + 1, cur + num, num, path + "+" + snum, res);
            dfs(s, target, i + 1, cur - num, -num, path + "-" + snum, res);
            dfs(s, target, i + 1, cur - last + last * num, last * num, path + "*" + snum, res);
        }
    }

    vector<string> addOperators(string num, int target) {
        vector<string> res;
        dfs(num, target, 0, 0, 0, "", res);
        return res;
    }
};

```

```java
class Solution {
    private void helper(String num, int target, int pos, long cur, String str, List<String> res, long last) {
        if (pos == num.length()) {
            if (cur == target)
                res.add(str);
            return;
        }
        for (int i = pos; i < num.length(); i++) {
            if (i != pos && num.charAt(pos) == '0') {
                break; // To prevent '05'
            }
            long val = Long.parseLong(num.substring(pos, i + 1));
            if (pos == 0) {
                helper(num, target, i + 1, val, str + val, res, val);
            } else {
                helper(num, target, i + 1, cur + val, str + "+" + val, res, val);
                helper(num, target, i + 1, cur - val, str + "-" + val, res, -val);
                helper(num, target, i + 1, cur - last + last * val, str + "*" + val, res, last * val);
            }
        }
    }

    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        if (num.length() == 0) {
            return res;
        }
        helper(num, target, 0, 0, "", res, 0);
        return res;
    }
}
```

## Thoughts

时间复杂度O(3 ^ N).


---

# 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://hao-fu-1.gitbook.io/oj/exhaustive-search/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.