753. Cracking the Safe

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;
    }
}