• 例如，正确的密码是 "345" ，并且你输入的是 "012345" ：
• 输入 0 之后，最后 3 位输入是 "0" ，不正确。
• 输入 1 之后，最后 3 位输入是 "01" ，不正确。
• 输入 2 之后，最后 3 位输入是 "012" ，不正确。
• 输入 3 之后，最后 3 位输入是 "123" ，不正确。
• 输入 4 之后，最后 3 位输入是 "234" ，不正确。
• 输入 5 之后，最后 3 位输入是 "345" ，正确，打开保险箱。

• 1 <= n <= 4

• 1 <= k <= 10

• 1 <= kn <= 4096

欧拉路

000
 001
  010
   100
    002
     020
      201
       011
        110
         101
          012
           120
            202
             021
              210
               102
                022
                 221
                  211
                   111
                    112
                     121
                      212
                       122
                        222
                         220
                          200

• 我们从节点 $$u$$ 开始，任意地经过还未经过的边，直到我们「无路可走」（死胡同）。此时我们一定回到了节点 $$u$$，这是因为所有节点的入度和出度都相等。

• 回到节点 $$u$$ 之后，我们得到了一条从 $$u$$ 开始到 $$u$$ 结束的回路，这条回路上仍然有些节点有未经过的出边。我么从某个这样的节点 $$v$$ 开始，继续得到一条从 $$v$$ 开始到 $$v$$ 结束的回路，再嵌入之前的回路中；

• 以此类推，直到没有节点有未经过的出边，此时我们就找到了一条欧拉回路。

class Solution {
public:
    string crackSafe(int n, int k) {
        unordered_set<int> vis;
        string ans;
        int highest = pow(10, n - 1);

        function<void(int)> dfs = [&](int node) {
            // 遍历当前节点的所有边
            for (int x = 0; x < k; x++) {
                int tmp = node * 10 + x;
                if (!vis.contains(tmp)) {
                    vis.insert(tmp);
                    // 递归下去
                    dfs(tmp % highest);
                    // 递归返回后，再更新，栈的结构。也就是一条路走到黑，路走完了。
                    ans += (x + '0');
                }
            }
        };

        dfs(0);
        ans += string(n - 1, '0');
        return ans;
    }
};

📎 参考

• 破解保险箱