> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/expression-add-operators.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/exhaustive-search/expression-add-operators.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.