1.题目基本信息

1.1.题目描述

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

注意，返回表达式中的操作数 不应该 包含前导零。

1.2.题目地址

https://leetcode.cn/problems/expression-add-operators/description/

2.解题方法

2.1.解题思路

回溯

2.2.解题步骤

第一步，构建回溯递归函数。在num[:i]范围内的表达式为expr，计算值为res，最后一个乘法值为mul的情况下；枚举num[i]及后面的连续数字组合，以及前置相邻的运算符号，并更新维护变量；并在递归出口处将合法的组合添加到result数组中

• 1.1.递归出口；i==n，即遍历完的情况，如果组合合法，则添加到result中

• 1.2.枚举后面的数以及当前的计算符号

  • 1.2.1.考虑当前字母为0的情况

  • 1.2.2.当前字符为num第一个字符的情况，此时无需枚举计算符号

  • 1.2.3.当前字符不是num第一个字符的情况，此时需要枚举计算符号

第二步，调用回溯，返回result

3.解题代码

python代码

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        # 思路：回溯
        n = len(num)
        # 第一步，构建回溯递归函数。在num[:i]范围内的表达式为expr，计算值为res，最后一个乘法值为mul的情况下；枚举num[i]及后面的连续数字组合，以及前置相邻的运算符号，并更新维护变量；并在递归出口处将合法的组合添加到result数组中
        result = []
        def backtrack(expr:list[str], i:int, res:int, mul:int):
            # 1.1.递归出口；i==n，即遍历完的情况，如果组合合法，则添加到result中
            if i == n:
                if res == target:
                    result.append("".join(expr))
                return
            # 1.2.枚举后面的数以及当前的计算符号
            index = len(expr)
            if i > 0:
                expr.append("")    # 记录计算符号的位置，并进行占位（后面会添加数字）
            val = 0
            for j in range(i, n):
                # 1.2.1.考虑当前字母为0的情况
                if j > i and num[i] == '0':
                    break
                val = val * 10 + int(num[j])
                expr.append(num[j])
                if i == 0:
                    # 1.2.2.当前字符为num第一个字符的情况，此时无需枚举计算符号
                    backtrack(expr, j + 1, val, val)
                else:
                    # 1.2.3.当前字符不是num第一个字符的情况，此时需要枚举计算符号
                    expr[index] = "+"; backtrack(expr, j + 1, res + val, val)
                    expr[index] = "-"; backtrack(expr, j + 1, res - val, -val)
                    expr[index] = "*"; backtrack(expr, j + 1, res - mul + mul * val, mul * val)
            del expr[index:]    # 回溯，这里用截取赋值会超时
        # 第二步，调用回溯，返回result
        backtrack([], 0, 0, 0)
        return result

4.执行结果