Description
https://leetcode.com/problems/cracking-the-safe/description/
https://leetcode.com/problems/cracking-the-safe/solution/
HashSet + Backtracking
class Solution {
public String crackSafe(int n, int k) {
int total = (int) Math.pow(k, n);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n - 1; ++i) {
sb.append("0");
}
Set<String> visited = new HashSet<>();
dfs(sb, n, k, visited, total);
return sb.toString();
}
private boolean dfs(StringBuilder sb, int n, int k, Set<String> visited, int total) {
if (visited.size() == total) {
return true;
}
int len = sb.length();
String prev = sb.substring(len - n + 1, len);
for (int i = 0; i < k; ++i) {
String curr = prev + i;
if (visited.contains(curr)) { // make sure pass each node only once
continue;
}
sb.append(i);
visited.add(curr);
if (dfs(sb, n, k, visited, total)) {
return true;
}
// backtracking
visited.remove(curr);
sb.setLength(len);
}
return false;
}
}
