以下是 LeetCode 753 “破解保险箱” 的 Java 解法，使用 Hierholzer 算法寻找欧拉回路，生成包含所有 n 位 k 进制密码的最短字符串。

import java.util.*;

public class Solution {
    public String crackSafe(int n, int k) {
        StringBuilder ans = new StringBuilder();
        Set<String> visited = new HashSet<>();
        // 起始节点为 n-1 个 '0'
        String start = String.join("", Collections.nCopies(n - 1, "0"));
        dfs(start, k, visited, ans);
        // 最后补上起始节点
        ans.append(start);
        return ans.toString();
    }

    private void dfs(String node, int k, Set<String> visited, StringBuilder ans) {
        for (int i = 0; i < k; i++) {
            String next = node + i; // 当前节点加上数字 i 构成一条边（即一个 n 位密码）
            if (!visited.contains(next)) {
                visited.add(next);
                // 递归进入下一个节点（去掉首位，保留后 n-1 位）
                dfs(next.substring(1), k, visited, ans);
                // 回溯时将当前边的最后一个数字加入结果
                ans.append(i);
            }
        }
    }
}

算法思路

· 将问题转化为图论：每个 n-1 位数字看作一个节点，每个 n 位密码看作一条从它的前 n-1 位指向后 n-1 位的有向边。
· 图中共有 k^(n-1) 个节点和 k^n 条边，每个节点出度和入度均为 k，因此存在欧拉回路。
· 从全 0 节点开始深度优先搜索，每访问一条新边就递归，并在回溯时记录边的最后一个数字，最后补上起始节点，即可得到经过所有边恰好一次的路径，对应的字符串即为答案。

复杂度分析

· 时间复杂度：O(k^n * n)，每条边被访问一次，每次字符串操作 O(n)。
· 空间复杂度：O(k^n * n)，用于存储访问过的边集合。