<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 possibility:
    def __init__(self, els, c, v):
        self.elements = els
        self.cumsum = c
        self.lastval = v
    def concat(self, newval):
        if self.elements[-1] == 0:
            return None
        if len(self.elements) == 1:
            cc = self.elements[-1] * 10 + newval
            return possibility([cc], 0, cc)
        else:
            newlv = self.lastval // self.elements[-1]
            cc = self.elements[-1] * 10 + newval
            newval = newlv * cc
            return possibility(self.elements[:-1] + [cc], self.cumsum, newval)
    def getsum(self):
        return self.cumsum + self.lastval
    def getstr(self):
        return "".join([str(el) for el in self.elements])

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        possibilities = []
        for i in range(len(num)):
            curnum = int(num[i])
            if i == 0:
                possibilities = [possibility([curnum], 0, curnum)]
                continue
            newpos = []
            for p in possibilities:
                if p is None:
                    continue
                els, c, v = p.elements, p.cumsum, p.lastval
                newpos.append(possibility(els + ["+", curnum], c + v, curnum))
                newpos.append(possibility(els + ["-", curnum], c + v, -curnum))
                newpos.append(possibility(els + ["*", curnum], c, v * curnum))
                newpos.append(p.concat(curnum))
            possibilities = newpos
        
        return [p.getstr() for p in possibilities if p and p.getsum() == target]

126300