> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/753.-cracking-the-safe.md).

# 753. Cracking the Safe

让生成一个最短的字符串能匹配任意的n位(每位的值范围为\[0,k - 1])的字符串密码。最短的字符串肯定是重复利用了当前字符串末尾 k - 1位再加上新生成的一位拼出一种可能的密码，比如n = 2, k = 2当前是00, 重复利用末尾的0和下一个可能的字符1拼，001就能cover 00和01两种情况了。一共有n^k个可能密码，因此DFS遍历所有可能性并当前path包含所有的可能密码==n^k时即是一种结果。可以证明这样的解一定存在且只需遍历一次就能找到，不过我不会证。

思路参考了[花花](https://link.zhihu.com/?target=http%3A//zxi.mytechroad.com/blog/graph/leetcode-753-cracking-the-safe/)的。

```cpp
/*
 * @lc app=leetcode id=753 lang=cpp
 *
 * [753] Cracking the Safe
 */
class Solution {
public:
    bool dfs(string &res, const int n, const int k, unordered_set<string> &path) {
        if (path.size() == pow(k, n)) return true;
        string cur = res.substr(res.length() - n + 1, n - 1);
        for (char c = '0'; c < '0' + k; ++c) {
            cur.push_back(c);
            if (!path.count(cur)) {
                res.push_back(c);
                path.insert(cur);
                if (dfs(res, n, k, path)) return true;
                path.erase(cur);
                res.pop_back();
            }
        }
        return false;
    }
    string crackSafe(int n, int k) {
        string res(n, '0');
        unordered_set<string> path{res};
        dfs(res, n, k, path);
        return res;
    }
};


```