Expression Operator Insertions

Problem Statement

Given a string consisting only of digits from 0 to 9 and a target number, find all possible ways to insert binary operators +, -, or * between the digits so that the resulting expression evaluates exactly to the target number.

Examples

Example 1:
Input: digits = "124", targetVal = 7
Output: ["1+2+4", "1*2+4"]

Example 2:
Input: digits = "221", targetVal = 5
Output: ["2+2+1", "2*2+1"]

Example 3:
Input: digits = "506", targetVal = 11
Output: ["5+0*6", "50-39"]

Example 4:
Input: digits = "11", targetVal = 2
Output: ["1+1", "1*1"]

Example 5:
Input: digits = "9876543", targetVal = 100
Output: []
    

Constraints

• 1 ≤ digits.length ≤ 12
• digits consists only of numeric characters ('0' - '9')
• -10⁹ ≤ targetVal ≤ 10⁹