'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List

# https://leetcode.com/problems/cracking-the-safe/discuss/153039/DFS-with-Explanations
class Solution:
    # T: O(k^(k^n)) -> close to O(k^n)
    # S: O(k^n)
    def crackSafe(self, n: int, k: int) -> str:
        total_size = k ** n
        self.ans = '0' * n # initialize pwd
        visited = {self.ans}
        if self.dfs(total_size, n, k, visited):
            return self.ans
        return ""
    
    def dfs(self, total_size, n, k, visited):
        if len(visited) == total_size: # tried all the passwd
            return True
        # prefix of the cur node, sharing the last n-1 digits of prev passwd
        lastDigits = self.ans[len(self.ans)-(n-1):] # last n-1 digits
        for c in range(k):
            newComb = lastDigits + str(c)
            if newComb not in visited:
                visited.add(newComb)
                self.ans += str(c)
                if self.dfs(total_size, n, k, visited):
                    return True
                visited.remove(newComb)
                self.ans = self.ans[:-1]
        return False