Google OA 面试真题解析：Expression Add Operators（表达式插入运算符）

Given a string num that contains only digits and an integer target, return all possibilities to insert binary operators +, -, or * between the digits so that the resulting expression evaluates to target.

You may not reorder or remove digits from num. Digits in num must stay in the same relative order. You can form multi-digit numbers as long as they do not have leading zeros.

Examples:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

这道题要求在数字字符串中插入加号、减号或乘号，枚举出所有能计算得到目标值的表达式。核心做法通常是深度优先搜索加回溯：从左到右切分数字，逐步构造当前表达式，并在递归中维护当前计算值以及上一段乘法项，才能正确处理乘法的优先级。需要特别注意前导零问题，像“05”这类数字片段不能作为合法数值。由于要输出所有可行解，时间复杂度本质上是指数级，适合用剪枝和状态维护来减少无效搜索。