<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 get_zeros_texts(self, count: int) -> list[str]:
        if count <= 2:
            if count <= 1:
                return ["0"] if count == 1 else []
            return ["0+0", "0-0", "0*0"]
        r = ["0+0", "0-0", "0*0"]
        for i in range(2, count):
            next_r = []
            for s in r:
                next_r.append(f"{s}+0")
                next_r.append(f"{s}-0")
                next_r.append(f"{s}*0")
            r = next_r
        return r

    def get_zero_texts_with_an_operator(self, count: int):
        r = ["0+", "0-", "0*"]
        if count == 1:
            return r
        for i in range(1, count):
            next_r = []
            for s in r:
                next_r.append(f"{s}0+")
                next_r.append(f"{s}0-")
                next_r.append(f"{s}0*")
            r = next_r
        return r

    def get_count_of_0_at_prefix(self, n: str):
        count = 0
        for i in range(len(n)):
            if n[i] == "0":
                count += 1
            else:
                break
        return count

    def get_results_if_v_in_n(self, n: str, v: int, abs_v: int, str_abs_v: str):
        # 001400, -14
        count_of_0_at_prefix = self.get_count_of_0_at_prefix(n)
        start_index = n.find(str_abs_v)
        if start_index == -1:
            return [], count_of_0_at_prefix
        elif start_index == 0 and v < 0:
            return [], count_of_0_at_prefix

        if count_of_0_at_prefix != start_index:
            return [], count_of_0_at_prefix

        end_index = start_index + len(str_abs_v)
        if end_index == len(n):
            if start_index == 0:
                return [n], count_of_0_at_prefix
            elif start_index == 1:
                return [f"0-{n[1:]}"], count_of_0_at_prefix

        # 检查是不是后面都是0
        for i in range(end_index, len(n)):
            if n[i] != "0":
                return [], count_of_0_at_prefix

        qianmian_zero_texts = self.get_zeros_texts(start_index)
        homian_zero_texts = self.get_zeros_texts(len(n) - end_index)

        sign = "-" if v < 0 else "+"
        r = []
        if not homian_zero_texts:
            r = [f"{qianmian_zero_text}{sign}{str_abs_v}" for qianmian_zero_text in qianmian_zero_texts]
            return r, count_of_0_at_prefix

        if v > 0 and not qianmian_zero_texts:
            for homian_zero_text in homian_zero_texts:
                r.append(f"{str_abs_v}+{homian_zero_text}")
                r.append(f"{str_abs_v}-{homian_zero_text}")
            return r, count_of_0_at_prefix

        for qianmian_zero_text in qianmian_zero_texts:
            for homian_zero_text in homian_zero_texts:
                r.append(f"{qianmian_zero_text}{sign}{str_abs_v}+{homian_zero_text}")
                r.append(f"{qianmian_zero_text}{sign}{str_abs_v}-{homian_zero_text}")
        return r, count_of_0_at_prefix

    def get_maximum_computed_value(self, mvl, mvr):
        smaller = mvl if mvl < mvr else mvr
        if smaller <= 1:
            return mvl + mvr
        else:
            return mvl * mvr

    def get_value(self, intn, start_index, end_index, powers_of_10):
        # 163 , 0, 2
        # (abs_v % 1000) // 10

        # print("abs_v, start_index, end_index, powers_of_10 = ", intn, start_index, end_index, powers_of_10)
        value_within_range = (intn % powers_of_10[start_index-1]) // powers_of_10[end_index-1]
        return value_within_range

    def compute(self, n, intn, v, abs_v):
        # print("===========")
        # print(f"n here = {n}")

        char_values = [ord(c) - 48 for c in n]
        length = len(n)

        first_char_value = char_values[0]


        # 263 : 263 % 100
        mvls = [char_values[0]]
        powers_of_10 = [1]
        for i in range(1, length):
            mvls.append(mvls[-1] * 10 + char_values[i])
            powers_of_10.append(powers_of_10[-1] * 10)
        powers_of_10.reverse()

        # print("rgerge powers_of_10 = ", powers_of_10)
        # exit()

        # print("n here = ", n )
        # print( mvl )
        # print( powersof10 )

        mvrs = [intn % powers_of_10[i] for i in range(length)]

        # print("At line 106 mvls = ", mvls, ", mvrs = " , mvrs  )
        # exit()
        result_tuples = [[] for i in range(length)]  # tuples of (expression, computed value, last value  )
        maximum_computed_value = self.get_maximum_computed_value(mvls[0],  mvrs[0])
        # print("maximum_computed_value = ", maximum_computed_value)

        if maximum_computed_value >= abs_v:
            result_tuples[0].append( (n[0], mvls[0], mvls[0]) )

        # print("results = ", results)
        for i in range(1, length - 1):
            maximum_computed_value = self.get_maximum_computed_value(mvls[i], mvrs[i])
            # print("maximum_computed_value = ", maximum_computed_value)
            if maximum_computed_value < abs_v:
                # print("fwefwefwef continue")
                continue

            # for j in range(i):
            i_plus_1 = i + 1
            rti = result_tuples[i]

            # print( i, ", ", n[i], ", " ,  n[:i],   )
            # print("fwefwef mvls[i] = ", mvls[i])
            # exit()
            if first_char_value > 0:
                rti.append((n[:i+1], mvls[i], mvls[i]))

                # print("fwfwef (n[:i+1], mvls[i], mvls[i]) = ", n[:i+1], mvls[i], mvls[i] )
                # exit()

            for j in range(1, i_plus_1):
                # i = 2 => (rs[0] and n1, n2)的组合  以及 (rs[1] and n2)
                if char_values[j] == 0 and j <= i_plus_1 - 2:
                    # two digits with first zero
                    continue

                value_from_j_to_i_plus_1 = self.get_value(intn, j, i_plus_1, powers_of_10)
                text_from_j_to_i_plus_1 = n[j:i_plus_1]

                # print(f'start_index = j = {j} , end_index = i_plus_1 = {i_plus_1}')
                # print("wegerge value_from_j_to_i_plus_1 = ", value_from_j_to_i_plus_1)
                # print("wegerge value_from_j_to_i_plus_1 = ", n[j:i_plus_1])
                # exit()
                # j = 1
                # print(f"j = {j}, n[j] = {n[j]}")
                # print(f"i = {i}, n[i] = {n[i]}")
                # 补上n[j:i]

                for expression, expression_value, last_value in result_tuples[j-1]:
                    # values
                    # print("fwefwf expression, expression_value, last_value = ",
                    #       expression, expression_value, last_value)
                    # print("n[j: i+1] = ", n[j: i+1])

                    qianmian_value = expression_value - last_value

                    # new_last_value_with_production = self.get_maximum_computed_value(last_value, value_from_j_to_i_plus_1)
                    new_last_value_with_production = last_value * value_from_j_to_i_plus_1

                    # maximum_possible_value_to_the_end = abs(qianmian_value) + abs(new_last_value_with_production * mvrs[i])

                    maximum_possible_value_to_the_end = abs(qianmian_value) + self.get_maximum_computed_value(  self.get_maximum_computed_value(abs(last_value), value_from_j_to_i_plus_1), mvrs[i])
                    if maximum_possible_value_to_the_end < abs_v:
                        continue

                    new_value_with_production = qianmian_value + new_last_value_with_production
                    rti.append((f"{expression}*{text_from_j_to_i_plus_1}", new_value_with_production, new_last_value_with_production ))

                    rti.append((f"{expression}+{text_from_j_to_i_plus_1}", expression_value + value_from_j_to_i_plus_1, value_from_j_to_i_plus_1))
                    rti.append((f"{expression}-{text_from_j_to_i_plus_1}", expression_value - value_from_j_to_i_plus_1, - value_from_j_to_i_plus_1))

                    # print("rtj = ",rtj)
                    # exit()

            # print("result_tuples= ",result_tuples, ", i = ", i)
            # exit()
            pass

        # print("fwefwef result_tuples = ", result_tuples)
        # exit()

        # rt_last = result_tuples[length - 1]
        result = []
        for j in range(1, length):
            if char_values[j] == 0 and j <= length - 2:
                continue

            value_from_j_to_i_plus_1 = self.get_value(intn, j, length, powers_of_10)
            text_from_j_to_i_plus_1 = n[j:length]

            for expression, expression_value, last_value in result_tuples[j - 1]:
                qianmian_value = expression_value - last_value

                new_last_value_with_production = last_value * value_from_j_to_i_plus_1

                new_value_with_production = qianmian_value + new_last_value_with_production
                if new_value_with_production == v:
                    result.append((f"{expression}*{text_from_j_to_i_plus_1}"))

                if expression_value + value_from_j_to_i_plus_1 == v:
                    result.append(f"{expression}+{text_from_j_to_i_plus_1}")

                if expression_value - value_from_j_to_i_plus_1 == v:
                    result.append(f"{expression}-{text_from_j_to_i_plus_1}" )
                pass

        # print("result = ", result)
        # exit()

        return result



    def addOperators(self, n: str, v: int) -> list[str]:
        length = len(n)
        if length == 1:
            return [n] if ord(n[0]) - 48 == v else []

        abs_v = abs(v)
        intn = int(n)
        if intn < abs_v:
            return []

        if intn == 0:
            if v == 0:
                return self.get_zeros_texts(length)
            return []

        str_abs_v = str(abs_v)
        results_for_v_in_n, c0 = self.get_results_if_v_in_n(n, v, abs_v, str_abs_v)
        if results_for_v_in_n:  # 00xx00
            return results_for_v_in_n

        if length == 2:
            n0, n1 = n
            v0, v1 = divmod(intn, 10)
            result = []
            if v0 + v1 == v:
                result.append(f"{n0}+{n1}")
            if v0 - v1 == v:
                result.append(f"{n0}-{n1}")
            if v0 * v1 == v:
                result.append(f"{n0}*{n1}")
            return result

        if c0 >= 2:
            homians = self.addOperators(n[c0 - 1:], v)
            if not homians:
                return []
            result = []
            zts = self.get_zero_texts_with_an_operator(c0 - 1)
            if len(homians) < len(zts):
                for homian in homians:
                    result.extend([f"{qianmian}{homian}" for qianmian in zts])
            else:
                for qianmian in zts:
                    result.extend([f"{qianmian}{homian}" for homian in homians])
            return result

        result = self.compute(n, intn, v, abs_v)
        return result


21600