<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>

'''
num = "123", target = 6

1) Generate all combination of numbers
For number, it can be
1,2,3 or 12, 3 or 1, 23, or 123

            []
1           12          123
2   23      3   
3
[1,2,3] [1, 23] [12, 3] [123]

For operataions, between each number, it can be +/ -/ */ //

            1
+       -     *     /   
            2
+       -       *       /
            3

1 + 2 + 3
1 + 2 - 3 x
1 + 2 * 3 x 
1 + 2 / 3 x 
'''
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        
        def generateCombinations(curr_str, curr_idx, total_length):
            if curr_idx == total_length:
                combinations.append(curr_str.copy())
                return 
            else:
                for i in range(total_length - curr_idx):
                    ## curr_idx = 0, total_length = 3
                    ## curr_str = []
                    ## curr_str [1] [12] [123]
                    ##        [0:1] [0:2] [0:3]
                    if len(num[curr_idx: curr_idx + 1 + i]) > 1 and num[curr_idx] == '0':
                        pass
                    else:
                        curr_str.append(num[curr_idx: curr_idx + 1 + i])
                        generateCombinations(curr_str, curr_idx + 1 + i, total_length)
                        curr_str.pop()      
            return

        def generateOperations(curr_str, curr_idx, total_length):
            if curr_idx == total_length - 1:
                operators.append(curr_str.copy())
                return
            else:
                for ch in "+-*":
                    curr_str.append(ch)
                    generateOperations(curr_str, curr_idx + 1, total_length)
                    curr_str.pop()
            return
            
        def calculate(nums, ops):
            '''
            Given list of integers length n and list of operations length n - 1,
            Return evaluated output
            i.e 
            Input: nums [2, 4, 6], ops [+, *]
            Output: 26 
            2 + 4 * 6 = 26

            [2] ops = +
            [2 4] ops = *
            [2 24] ops = done
            '''
            stack = []
            p1, p2 = 0, 0

            if len(nums) == 1:
                return nums

            while p1 < len(nums) and p2 < len(ops):
                if not stack:
                    stack.append(int(nums[p1]))
                    p1 += 1
                else:
                    if ops[p2] == '+':
                        stack.append(int(nums[p1]))
                    elif ops[p2] == '-':
                        stack.append(-int(nums[p1]))
                    elif ops[p2] == '*':
                        stack[-1] = stack[-1] * int(nums[p1])
                    p1 += 1
                    p2 += 1
            return sum(stack)
        
        def generateCombinedString(nums, ops):
            combstring = []
            p1, p2 = 0, 0
            while p1 < len(nums) or p2 < len(ops):
                if p1 < len(nums):
                    combstring.append(nums[p1])
                    p1 += 1
                if p2 < len(ops):
                    combstring.append(ops[p2])
                    p2 += 1
            return "".join(combstring)

        if num == str(target):
            return [num]

        combinations = []
        generateCombinations([], 0, len(num))

        output = []
        for comb in combinations:
            operators = []
            generateOperations([], 0, len(comb))
    
            for op in operators:
                if calculate(comb, op) == target:
                    output.append(generateCombinedString(comb, op))

        return output
19700