<p>There is a safe protected by a password. The password is a sequence of <code>n</code> digits where each digit can be in the range <code>[0, k - 1]</code>.</p>

<p>The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the <strong>most recent </strong><code>n</code><strong> digits</strong> that were entered each time you type a digit.</p>

<ul>
	<li>For example, the correct password is <code>&quot;345&quot;</code> and you enter in <code>&quot;012345&quot;</code>:

	<ul>
		<li>After typing <code>0</code>, the most recent <code>3</code> digits is <code>&quot;0&quot;</code>, which is incorrect.</li>
		<li>After typing <code>1</code>, the most recent <code>3</code> digits is <code>&quot;01&quot;</code>, which is incorrect.</li>
		<li>After typing <code>2</code>, the most recent <code>3</code> digits is <code>&quot;012&quot;</code>, which is incorrect.</li>
		<li>After typing <code>3</code>, the most recent <code>3</code> digits is <code>&quot;123&quot;</code>, which is incorrect.</li>
		<li>After typing <code>4</code>, the most recent <code>3</code> digits is <code>&quot;234&quot;</code>, which is incorrect.</li>
		<li>After typing <code>5</code>, the most recent <code>3</code> digits is <code>&quot;345&quot;</code>, which is correct and the safe unlocks.</li>
	</ul>
	</li>
</ul>

<p>Return <em>any string of <strong>minimum length</strong> that will unlock the safe <strong>at some point</strong> of entering it</em>.</p>

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

<pre>
<strong>Input:</strong> n = 1, k = 2
<strong>Output:</strong> &quot;10&quot;
<strong>Explanation:</strong> The password is a single digit, so enter each digit. &quot;01&quot; would also unlock the safe.
</pre>

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

<pre>
<strong>Input:</strong> n = 2, k = 2
<strong>Output:</strong> &quot;01100&quot;
<strong>Explanation:</strong> For each possible password:
- &quot;00&quot; is typed in starting from the 4<sup>th</sup> digit.
- &quot;01&quot; is typed in starting from the 1<sup>st</sup> digit.
- &quot;10&quot; is typed in starting from the 3<sup>rd</sup> digit.
- &quot;11&quot; is typed in starting from the 2<sup>nd</sup> digit.
Thus &quot;01100&quot; will unlock the safe. &quot;10011&quot;, and &quot;11001&quot; would also unlock the safe.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 4</code></li>
	<li><code>1 &lt;= k &lt;= 10</code></li>
	<li><code>1 &lt;= k<sup>n</sup> &lt;= 4096</code></li>
</ul>

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        # Generate all possible n-length combinations of digits from 0 to k-1
        # Create a range of numbers as strings
        number_strings = map(str, range(k))

        # Generate all possible products with repetition
        all_combinations = product(number_strings, repeat=n)

        # Join each tuple of characters into a single string
        joined_combinations = map("".join, all_combinations)

        # Convert the result to a set
        perms = set(joined_combinations)

        # This will store the result in reverse order as we perform DFS
        res = []

        # Start with the initial combination of all zeros
        start = "0" * n

        # Remove the start combination from the set of permutations since we're starting from it
        perms.remove(start)

        # Start the DFS traversal from the initial combination
        self.dfs(start, k, perms, res)

        # Join the result list and add the starting combination to complete the Eulerian circuit
        return "".join(res) + start

    def dfs(self, n: str, k: int, perms: set, res: list):
        """
        This method performs Depth-First Search (DFS) to explore all possible combinations,
        and ensures that each combination is visited exactly once to form an Eulerian circuit.

        :param n: The current combination being explored
        :param k: Number of possible digits (0 to k-1)
        :param perms: Set of all unvisited combinations
        :param res: List to store the result in reverse order
        """

        # If all permutations have been visited, stop the DFS
        if not perms:
            return

        # Explore all possible digits (0 to k-1)
        for d in map(str, range(k)):
            # Create the next combination by appending the digit `d` and removing the first character
            next_ = (n + d)[1:]

            # If the next combination has not been visited yet, continue the DFS from this combination
            if next_ in perms:
                # Mark this combination as visited by removing it from the set
                perms.remove(next_)

                # Recursively perform DFS on the next combination
                self.dfs(next_, k, perms, res)

                # After all edges from this node are visited, add the digit to the result
                res.append(d)

18400