<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 __init__(self):
        self.combos = []
        self.ops = ["","*","+","-"]
        self.digs = {'0','1','2','3','4','5','6','7','8','9'}

    def addOperators(self, num: str, target: int) -> list[str]:
        ans = []
        all_combos = self.createCombos(num)
        #print(all_combos)
        for combo in all_combos:
            if eval(combo) == target: 
                ans.append(combo)
        return ans 
    
    def getOps(self, n:int, k:int, inp: list[int]):
        if n == k: 
            self.combos.append(inp)
            return 
        for op in self.ops: 
            self.getOps(n,k+1,inp+[op])
        

    def createCombos(self,num:str) -> list[str]:
        self.getOps(len(num)-1,0,[])
        ans = [] 
        for combo in self.combos: 
            to_add = ""
            for i,op in enumerate(combo):
                to_add = to_add + num[i] + op
            to_add += num[-1]
            #print(to_add)
            if self.isLeading(to_add) == False:
                ans.append(to_add)
        #print(ans)
        return ans 
    
    def isLeading(self, exp: str) -> str: 
        switch = True
        for i,char in enumerate(exp):
            if switch == True and char == '0':
                if i<len(exp) - 1: 
                    if exp[i+1] in self.digs:
                        return True 
            elif char in self.digs:
                switch = False 
                continue 
            elif char not in self.digs:
                switch = True 

        return False 

78000