753. Cracking the Safe

There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].

The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.

For example, the correct password is "345" and you enter in "012345":
After typing 0, the most recent 3 digits is "0", which is incorrect.
After typing 1, the most recent 3 digits is "01", which is incorrect.
After typing 2, the most recent 3 digits is "012", which is incorrect.
After typing 3, the most recent 3 digits is "123", which is incorrect.
After typing 4, the most recent 3 digits is "234", which is incorrect.
After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

Return any string of minimum length that will unlock the safe at some point of entering it.

Example 1:

Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.

Example 2:

Input: n = 2, k = 2
Output: "01100"
Explanation: For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.

Constraints:

1 <= n <= 4
1 <= k <= 10
1 <= kn <= 4096

Solution:

class Solution {
    public String crackSafe(int n, int k) {
        int totalRequired = (int) Math.pow(k, n); // (2, 2) = 2^2 = 4
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++){
            sb.append('0'); // sb: 00
        }

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

        dfs(n, k, totalRequired - 1, seen, sb); // 2, 2, 3, <00>, '00'
        return sb.toString();
    }

    private boolean dfs(int n, int k, int totalRequired, Set<String> seen, StringBuilder prev){
        // 2, 2, 3, <00, 01, 10, 01>, '00'
        if (totalRequired == 0){ // // If all required sequences have been added
            return true;
        }
        // // 2, 2, 3-1 =2 , <00, 01>, '001'
        //  2, 2,1 , 0010

        // Try appending each digit from 0 to k-1
        for (int i = 0; i < k; i++){ // i = 0 ; 2 
            prev.append(i); //'001'  // 0010 //00100// 00101
            // // Get the last n digits
            String curLock = prev.toString().substring(prev.length() - n, prev.length());
            // 3-2 = 1, 1 ,3    1,2: 001    01 // 10  // 00  // 01
            if (!seen.contains(curLock)){// Check if this sequence has been seen
                seen.add(curLock); // 01 // 10 // 01
                if (dfs(n, k, totalRequired - 1, seen, prev)){ // Recursively continue DFS
                    return true; // 2, 2, 3-1 =2 , <00, 01>, '001'
                    // 2, 2,2 -1 = 1 , 0010
                }
                // // Backtrack
                seen.remove(curLock);
            }
            //// Remove last digit before next iteration
            prev.deleteCharAt(prev.length() - 1);
        }

        return false;
    }
}

I cannot understand the question again...

n个数字

k^n 2^2 = 4

k^n 2^1 = 1

示例：n=2n = 2n=2, k=2k = 2k=2

目标： 找到一个字符串，它在某个位置上包含所有可能的两位数组合（00, 01, 10, 11）。

步骤 1: 初始化

totalRequired = k^n = 2^2 = 4，需要找到 4 个独特的组合。

初始字符串 sb = "00"，因为我们开始时需要一个长度为 nnn 的起点。

初始化 seen = {"00"}，表示已经见过的组合是 "00"。

步骤 2: 递归调用 DFS

调用 dfs(n, k, totalRequired - 1, seen, sb)，在这种情况下为 dfs(2, 2, 3, {"00"}, "00")。

递归过程：

第一次递归: - prev = "00"，当前序列。 - totalRequired = 3，还需要找到 3 个独特的组合。 - 尝试添加数字 0:

prev = "000"，截取最后两位，得到 "00"，已在 seen 中，所以回退。

尝试添加数字 1:

prev = "001"，截取最后两位，得到 "01"，不在 seen 中。

更新 seen = {"00", "01"}。

递归调用 dfs(2, 2, 2, {"00", "01"}, "001")。

第二次递归: - prev = "001"，当前序列。 - totalRequired = 2，还需要找到 2 个独特的组合。 - 尝试添加数字 0:

prev = "0010"，截取最后两位，得到 "10"，不在 seen 中。

更新 seen = {"00", "01", "10"}。

递归调用 dfs(2, 2, 1, {"00", "01", "10"}, "0010")。

第三次递归: - prev = "0010"，当前序列。 - totalRequired = 1，还需要找到 1 个独特的组合。 - 尝试添加数字 0:

prev = "00100"，截取最后两位，得到 "00"，已在 seen 中，所以回退。

尝试添加数字 1:

prev = "00101"，截取最后两位，得到 "11"，不在 seen 中。

更新 seen = {"00", "01", "10", "11"}。

递归调用 dfs(2, 2, 0, {"00", "01", "10", "11"}, "00101")。

第四次递归: - prev = "00101"，当前序列。 - totalRequired = 0，所有组合都已找到。 - 返回 true，表示已找到所有组合。

步骤 3: 返回结果

DFS 成功，返回最终的字符串 sb.toString()，得到 "00110" 或其他可能的解。

总结

最终字符串 "00110" 在某个位置上包含所有可能的两位组合：00, 01, 10, 11。这个例子完整地演示了递归调用和回溯如何帮助找到所有可能的组合。每次尝试未成功的路径时，通过回溯机制撤销一步，直到找到正确的路径。

汉密尔顿路径

https://en.wikipedia.org/wiki/De_Bruijn_sequence

理解难证明太难了实现反而是比较简单的