题目描述

给定一个只包含0-9的字符串，以及一个目标值。在数字之间可以添加二元操作符+, -，*或者不填，使得表达式的值等于目标值。返回所有合法方案。

样例1

输入：num = "123", target = 6
输出：["1+2+3", "1*2*3"] 

样例2

输入：num = "232", target = 8
输出：["2*3+2", "2+3*2"]

样例3

输入：num = "105", target = 5
输出：["1*0+5","10-5"]

样例4

输入：num = "00", target = 0
输出：["0+0", "0-0", "0*0"]

样例5

输入：num = "3456237490", target = 9191
输出：[]

算法

(DFS) $O(n4^n)$

基本思路是暴力枚举所有表达式方案:

• 每两个数字之间可以不填任何字符，也可以填加减乘，所以每个间隔有4种方案，直接暴力枚举所有方案即可。

本题的难点在于常数优化，如果实现方式不好，那么本题就很容易超时。总结下来一共两点：

• 如果先暴搜出所有表达式的形式，然后再用表达式求值的模板去求解，那么会超时；
• 记录方案时如果每次复制整个数组，那么会超时；

为了能尽量优化常数，我们在递归过程中尽量不要使用栈来维护表达式。本题中我们维护如下不变式：

• $a + b \times (\;)$，其中括号中的数是我们枚举的下一个数；

然后分类讨论下一个运算符，其中 $c$ 是我们枚举的括号中的数：

• 下一个运算符是加号，那么 $a + b \times (c) + () = (a + b \times c) + 1 \times ()$;
• 下一个运算符是减号，那么 $a + b \times (c) - () = (a + b \times c) + (-1) \times ()$;
• 下一个运算符是乘号，那么 $a + b \times (c) \times () = a + (b \times c) \times ()$;

为了方便，我们在表达式最后统一添加一个加号，那么最终不变式就会变成 $a + 1 \times ()$，所以 $a$ 就是我们枚举的表达式的值，判断一下和target是否相等即可。

时间复杂度分析

假设一共有 $n$ 个字符，那么我们一共会枚举 $n - 1$ 个间隙，每个间隙有4种方案，所以一共有 $4 ^ {n - 1}$ 种方案，每种方案被记录下来还需要 $O(n)$ 的计算量，所以总时间复杂度是 $O(nn^4)$。

C++ 代码

typedef long long LL;

class Solution {
public:
    vector<string> ans;
    string path;

    vector<string> addOperators(string num, int target) {
        path.resize(100);
        dfs(num, 0, 0, 0, 1, target);
        return ans;
    }

    void dfs(string& num, int u, int len, LL a, LL b, LL target) {
        if (u == num.size()) {
            if (a == target) {
                ans.push_back(path.substr(0, len - 1));
            }
        } else {
            LL c = 0;
            for (int i = u; i < num.size(); i ++ ) {
                c = c * 10 + num[i] - '0';
                path[len ++ ] = num[i];
                path[len] = '+';
                dfs(num, i + 1, len + 1, a + b * c, 1, target);
                if (i + 1 < num.size()) {
                    path[len] = '-';
                    dfs(num, i + 1, len + 1, a + b * c, -1, target);
                }
                if (i + 1 < num.size()) {
                    path[len] = '*';
                    dfs(num, i + 1, len + 1, a, b * c, target);
                }
                if (num[u] == '0') break;
            }
        }
    }
};