Expression Add Operators

I picked this up while doing a Meta E5 onsite refresh and the gotcha that made me redo the solution at the whiteboard was operator precedence. When you append a *, you cannot just multiply the running total by the new operand. You have to remember the LAST additive operand and undo its contribution to the running sum before applying the multiplication. My first pass missed this and produced beautiful nonsense for 1 + 2 * 3. The interviewer's nudge was a single short question: "What does * actually attach to?" The catalog covered basic-calculator (which EVALUATES a fixed expression) but it skipped this constructive variant, where you GENERATE every expression and filter by value. The two problems share a vocabulary, but the state you carry through the recursion is completely different.

Expression Add Operators

Given a string num that contains only digits and an integer target, return all expressions that you can build by inserting the binary operators +, -, or * between the digits of num so that the resulting expression evaluates to target. Operands in the returned expressions should not contain leading zeros (so "05" is invalid, but the standalone "0" is fine).

Return the answers in any order.

Examples

Example 1:

• Input: num = "123", target = 6
• Output: ["1*2*3", "1+2+3"]
• Explanation: Both expressions evaluate to 6.

Example 2:

• Input: num = "232", target = 8
• Output: ["2*3+2", "2+3*2"]
• Explanation: Both respect standard *-before-+ precedence; both evaluate to 8. A naive left-to-right evaluator would compute (2 + 3) * 2 = 10 for the second expression and miss the match.

Example 3:

• Input: num = "3456237490", target = 9191
• Output: []
• Explanation: No insertion of operators produces 9191.

Example 4:

• Input: num = "105", target = 5
• Output: ["1*0+5", "10-5"]
• Explanation: "0+5" is allowed (the standalone "0" is a valid operand); "05" is not. "10" is allowed because it has no leading zero.

Constraints

• 1 <= num.length <= 10.
• num consists of only digits.
• -2^31 <= target <= 2^31 - 1.

Follow-up

Why does the recursion need to track BOTH the running total AND the last operand separately? Because * binds tighter than + and -: a + b * c does NOT equal (a + b) * c. To extend the prefix a + b with * c, we must compute a + b * c = (a + b) - b + b * c, which requires knowing b (the last additive term). Tracking it explicitly lets each multiplication step do constant-time updates instead of re-parsing the prefix. The same trick generalizes to chained multiplication: extending a + b * c with * d becomes (a + b * c) - (b * c) + (b * c * d), where the running last-operand is now b * c. With num.length capped at 10, the worst-case fan-out is 4^9 = 262144 recursion paths (three operator choices plus the implicit no-op of extending the current operand by one digit), which is comfortably fast in either language with no memoization required.