<p>Given a string <code>num</code> that contains only digits and an integer <code>target</code>, return <em><strong>all possibilities</strong> to insert the binary operators </em><code>&#39;+&#39;</code><em>, </em><code>&#39;-&#39;</code><em>, and/or </em><code>&#39;*&#39;</code><em> between the digits of </em><code>num</code><em> so that the resultant expression evaluates to the </em><code>target</code><em> value</em>.</p>

<p>Note that operands in the returned expressions <strong>should not</strong> contain leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;123&quot;, target = 6
<strong>Output:</strong> [&quot;1*2*3&quot;,&quot;1+2+3&quot;]
<strong>Explanation:</strong> Both &quot;1*2*3&quot; and &quot;1+2+3&quot; evaluate to 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;232&quot;, target = 8
<strong>Output:</strong> [&quot;2*3+2&quot;,&quot;2+3*2&quot;]
<strong>Explanation:</strong> Both &quot;2*3+2&quot; and &quot;2+3*2&quot; evaluate to 8.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;3456237490&quot;, target = 9191
<strong>Output:</strong> []
<strong>Explanation:</strong> There are no expressions that can be created from &quot;3456237490&quot; to evaluate to 9191.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 10</code></li>
	<li><code>num</code> consists of only digits.</li>
	<li><code>-2<sup>31</sup> &lt;= target &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
  def addOperators(self, num: str, target: int) -> List[str]:
    N = len(num)
    dp = {}

    # is_first_op: track whether we have added the first op: "+".
    def recurse(i, prev_num, cur_num, value, is_first_op=True):
      # Done processing all the digits in num
      if i == N:
        # If the final value == target expected AND
        # no operand/cur_num is left unprocessed
        if value == target and cur_num == 0:
          # NOTE: we do `res[1:]` by ignoring the first "+" in the results.
          # The results are always like ['+1+2+3', '+1*2*3'].
          return [""]
        return []

      state = (i, prev_num, cur_num, value)
      if state in dp:
        return dp[state]

      # Extending the current operand/num by one digit
      cur_num = cur_num * 10 + int(num[i])
      str_op = str(cur_num)
      res_list = []

      # To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a
      # valid operand / cur_num.
      if cur_num > 0:
        # Continue building the current num.
        tmp = recurse(i + 1, prev_num, cur_num, value, is_first_op)
        res_list = copy.deepcopy(tmp)

      # ADDITION
      prefix = str_op if is_first_op else f'+{str_op}'
      temp = recurse(i + 1, cur_num, 0, value + cur_num, False)
      for res in temp:
        res_list.append(f'{prefix}{res}')

      # Can subtract or multiply only if there are some previous operands
      if is_first_op:
        dp[state] = res_list
        return dp[state]
      # SUBTRACTION
      prefix = f'-{str_op}'
      temp = recurse(i + 1, -cur_num, 0, value - cur_num, False)
      for res in temp:
        res_list.append(f'{prefix}{res}')

      # MULTIPLICATION
      prefix = f'*{str_op}'
      temp = recurse(i + 1, cur_num * prev_num, 0, value - prev_num + (cur_num * prev_num), False)
      for res in temp:
        res_list.append(f'{prefix}{res}')

      dp[state] = res_list
      return res_list

    res_list = recurse(0, 0, 0, 0)
    return res_list
36100