753. Cracking the Safe

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:

Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.

Example 2:

Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.

Note:

1. n will be in the range [1, 4].
2. k will be in the range [1, 10].
3. k^n will be at most 4096.

一刷
题解：密码的长度为n, 我们会在[0, ..., k-1]这k个digit中选取数字， 并且不停地往后面添加，直到最后的n个digit与密码match, 求最小的长度的input一定可以解开密码。

DFS可以做的原因是，确保每一次都可以形成一次状态转移，否则pruning. 因为是欧拉回路和哈密顿图，所以可以保证存在每个状态只经过一次的路径。

欧拉回路：一笔画，每个边只经过一次。因为入度(n) == 出度(n),可以证明为欧拉回路。
哈密顿图：指定的起点前往指定的终点，途中经过所有其他节点且只经过一次，对于顶点个数大于2的图，如果图中任意不相邻的两点度的和大于或等於顶点总数，那这个图一定是哈密尔顿图。

如何判断一个图是不是哈密顿图？w(G-S)>|S|
S表示点的非空子集，|S|表示子集包括的点的数目

class Solution {
    public String crackSafe(int n, int k) {
        StringBuilder sb = new StringBuilder();
        int total = (int) (Math.pow(k, n));
        for (int i = 0; i < n; i++) sb.append('0');

        Set<String> visited = new HashSet<>();
        visited.add(sb.toString());

        dfs(sb, total, visited, n, k);

        return sb.toString();
    }

    private boolean dfs(StringBuilder sb, int goal, Set<String> visited, int n, int k) {
        if (visited.size() == goal) return true;
        String prev = sb.substring(sb.length() - n + 1, sb.length());//the next n-1 digit
        for(int i=0; i<k; i++){
            String cur = prev + i;
            if(visited.contains(cur)) continue;//确保每次添加，都形成了一次状态转移
            visited.add(cur);
            sb.append(i);
            if(dfs(sb, goal, visited, n, k)) return true;//不停throw,找到第一个就返回
            else{
                visited.remove(cur);
                sb.delete(sb.length()-1, sb.length());
            }
        }
        return false;
    }

}