# 753. Cracking the Safe

• Time: $O(k^{k^n}) \to O(k^n)$
• Space: $O(k^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: string crackSafe(int n, int k) { string ans(n, '0'); dfs(pow(k, n), n, k, {ans}, ans); return ans; } private: bool dfs(int passwordSize, int n, int k, unordered_set&& seen, string& path) { if (seen.size() == passwordSize) return true; string prefix = path.substr(path.length() - n + 1); for (char c = '0'; c < '0' + k; ++c) { prefix.push_back(c); if (!seen.count(prefix)) { seen.insert(prefix); path.push_back(c); if (dfs(passwordSize, n, k, move(seen), path)) return true; path.pop_back(); seen.erase(prefix); } prefix.pop_back(); } return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public String crackSafe(int n, int k) { final String allZeros = "0".repeat(n); StringBuilder sb = new StringBuilder(allZeros); dfs((int) Math.pow(k, n), n, k, new HashSet<>(Arrays.asList(allZeros)), sb); return sb.toString(); } private boolean dfs(int passwordSize, int n, int k, Set seen, StringBuilder path) { if (seen.size() == passwordSize) return true; StringBuilder prefix = new StringBuilder(path.substring(path.length() - n + 1)); for (char c = '0'; c < '0' + k; ++c) { prefix.append(c); final String prefixStr = prefix.toString(); if (!seen.contains(prefixStr)) { seen.add(prefixStr); path.append(c); if (dfs(passwordSize, n, k, seen, path)) return true; path.deleteCharAt(path.length() - 1); seen.remove(prefixStr); } prefix.deleteCharAt(prefix.length() - 1); } return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def crackSafe(self, n: int, k: int) -> str: passwordSize = k**n path = '0' * n seen = set() seen.add(path) def dfs(path: str) -> str: if len(seen) == passwordSize: return path for c in map(str, range(k)): node = path[-n + 1:] + c if n > 1 else c if node not in seen: seen.add(node) res = dfs(path + c) if res: return res seen.remove(node) return dfs(path)