753. Cracking the Safe

class Solution {
    public String crackSafe(int n, int k) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) sb.append("0");
        set.add(sb.toString());
        dfs(n, k, sb);
        return str;
    }

    boolean dfs(int n, int k, StringBuilder sb)
    {
        if(set.size() == (int) Math.pow(k, n))
        {
            str = sb.toString();
            return true;
        }
        int len = sb.length();
        String sub = sb.substring(len - n + 1);
        for(int i = 0; i < k; i++)
        {
            String next = sub + i;
            if(set.contains(next)) continue;
            sb.append(i);
            set.add(next);
            if(dfs(n, k, sb)) return true;
            sb.deleteCharAt(len);
            set.remove(next);
        }
        return false;
    }

    String str = "";

    Set<String> set = new HashSet<>();
}