<p>We had some 2-dimensional coordinates, like <code>&quot;(1, 3)&quot;</code> or <code>&quot;(2, 0.5)&quot;</code>. Then, we removed all commas, decimal points, and spaces and ended up with the string s.</p>

<ul>
	<li>For example, <code>&quot;(1, 3)&quot;</code> becomes <code>s = &quot;(13)&quot;</code> and <code>&quot;(2, 0.5)&quot;</code> becomes <code>s = &quot;(205)&quot;</code>.</li>
</ul>

<p>Return <em>a list of strings representing all possibilities for what our original coordinates could have been</em>.</p>

<p>Our original representation never had extraneous zeroes, so we never started with numbers like <code>&quot;00&quot;</code>, <code>&quot;0.0&quot;</code>, <code>&quot;0.00&quot;</code>, <code>&quot;1.0&quot;</code>, <code>&quot;001&quot;</code>, <code>&quot;00.01&quot;</code>, or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like <code>&quot;.1&quot;</code>.</p>

<p>The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma.)</p>

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

<pre>
<strong>Input:</strong> s = &quot;(123)&quot;
<strong>Output:</strong> [&quot;(1, 2.3)&quot;,&quot;(1, 23)&quot;,&quot;(1.2, 3)&quot;,&quot;(12, 3)&quot;]
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;(0123)&quot;
<strong>Output:</strong> [&quot;(0, 1.23)&quot;,&quot;(0, 12.3)&quot;,&quot;(0, 123)&quot;,&quot;(0.1, 2.3)&quot;,&quot;(0.1, 23)&quot;,&quot;(0.12, 3)&quot;]
<strong>Explanation:</strong> 0.0, 00, 0001 or 00.01 are not allowed.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;(00011)&quot;
<strong>Output:</strong> [&quot;(0, 0.011)&quot;,&quot;(0.001, 1)&quot;]
</pre>

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

<ul>
	<li><code>4 &lt;= s.length &lt;= 12</code></li>
	<li><code>s[0] == &#39;(&#39;</code> and <code>s[s.length - 1] == &#39;)&#39;</code>.</li>
	<li>The rest of <code>s</code> are digits.</li>
</ul>

class Solution:
    def ambiguousCoordinates(self, s: str) -> List[str]:
        s = s[1:-1]
        n = len(s)

        result = []
        def float_to_str(f):
            float_string = repr(f)
            if 'e' in float_string:  # detect scientific notation
                digits, exp = float_string.split('e')
                digits = digits.replace('.', '').replace('-', '')
                exp = int(exp)
                zero_padding = '0' * (abs(int(exp)) - 1)  # minus 1 for decimal point in the sci notation
                sign = '-' if f < 0 else ''
                if exp > 0:
                    float_string = '{}{}{}.0'.format(sign, digits, zero_padding)
                else:
                    float_string = '{}0.{}{}'.format(sign, zero_padding, digits)
            return float_string

        def backtrack(idx, had_comma, had_first_dot, had_second_dot, candidate):
            nonlocal result
            if idx == n-1:
                if not had_comma:
                    return
                candidate.append(s[idx])
                val = "".join(candidate)
                val_1, val_2 = val.split(", ")
                if "." in val_1:
                    val_1_good = val_1 == float_to_str(float(val_1))
                    val_1_good = val_1_good and (float(val_1) != 0.0)
                    val_1_good = val_1_good and (float(val_1) != int(float(val_1)))
                else:
                    val_1_good = val_1 == str(int(val_1))
                if "." in val_2:
                    val_2_good = val_2 == float_to_str(float(val_2))
                    val_2_good = val_2_good and (float(val_2) != 0.0)
                    val_2_good = val_2_good and (float(val_2) != int(float(val_2)))
                else:
                    val_2_good = val_2 == str(int(val_2))

                if val_1_good and val_2_good:
                    result.append("(" + val + ")")
                candidate.pop()
                return

            candidate.append(s[idx])
            if not had_comma:
                if not (candidate[-1] == "0" and len(candidate) == 1):
                    backtrack(idx+1, False, had_first_dot, had_second_dot, candidate)
                candidate.append(",")
                candidate.append(" ")
                backtrack(idx+1, True, had_first_dot, False, candidate)
                candidate.pop()
                candidate.pop()
                if not had_first_dot:
                    candidate.append(".")
                    backtrack(idx+1, False, True, False, candidate)
                    candidate.pop()
            else:
                if not had_second_dot:
                    candidate.append(".")
                    backtrack(idx+1, True, had_first_dot, True, candidate)
                    candidate.pop()
                if "".join(candidate[-2]) != " 0":
                    backtrack(idx+1, True, had_first_dot, had_second_dot, candidate)
            candidate.pop()
        backtrack(0, False, False, False, [])
        return result
                






        
17200