> 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

https\://leetcode.com/problems/expression-add-operators/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.
>
> 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).