给表达式添加运算符

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回 所有 能够得到 target 的表达式。
注意，返回表达式中的操作数 不应该 包含前导零。

  • 输入: num = “123”, target = 6

  • 输出: [“1+2+3”, “123”]
    解释: “123” 和 “1+2+3” 的值都是 6。

  • 输入: num = “232”, target = 8

  • 输出: [“23+2”, “2+32”]
    解释: “23+2” 和 “2+32” 的值都是 8。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var addOperators = function(num, target) {
    const arr = [];
    const dfs = (str, idx, nextNum, res, nextRes) => {
        if (idx !== num.length) {
            let newRes = res;
            let newNextRes = nextRes;
            const currentNum = Number(num[idx]);
            // *
            newNextRes = nextRes * currentNum;
            newRes = res - nextRes + newNextRes;
            dfs(str + "*" + num[idx], idx + 1, currentNum, newRes, newNextRes);
            // +
            newNextRes = currentNum;
            newRes = res + newNextRes;
            dfs(str + "+" + num[idx], idx + 1, currentNum, newRes, newNextRes);
            // -
            newNextRes = -currentNum;
            newRes = res + newNextRes;
            dfs(str + "-" + num[idx], idx + 1, currentNum, newRes, newNextRes);
            // ''
            const newNextNum = nextNum * 10 + currentNum;
            newNextRes = (nextRes / nextNum) * newNextNum;
            newRes = res - nextRes + newNextRes;
            if (newNextNum !== 0) {
                dfs(str + num[idx], idx + 1, newNextNum, newRes, newNextRes);
            }
        } else {
            if (res === target) arr.push(str);
        }
    };
    dfs(num[0], 1, Number(num[0]), Number(num[0]), Number(num[0]));
    return arr;
};