# 753. Cracking the Safe

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

While entering a password, the last `n` digits entered will automatically be matched against the correct password.

For example, assuming the correct password is `"345"`, if you type `"012345"`, the box will open because the correct password matches the suffix of the entered password.

Return any password of **minimum length** that is guaranteed to open the box at some point of entering it.

**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`.

```cpp
// Greedy Method
string crackSafe(int n, int k) { // time: O(k^(n + 1)); space: O(k^n)
    string res = string(n, '0'); // start with n 0s
    unordered_set<string> visited({res});
    for (int i = 0; i < pow(k, n); ++i) {
        string pre = res.substr(res.size() - (n - 1), n - 1);
        for (int j = k - 1; j >= 0; --j) {
            string cur = pre + to_string(j);
            if (!visited.count(cur)) {
                visited.insert(cur);
                res += to_string(j);
                break;
            }
        }
    }
    return res;
}
```

```cpp
// Greedy Method with Recursion
void helper(int n, int k, int total, unordered_set<string>& visited, string& res) {
    if (visited.size() == total) return;
    string pre = res.substr(res.size() - (n - 1), n - 1);
    for (int i = k - 1; i >= 0; --i) {
        string cur = pre + to_string(i);
        if (visited.count(cur)) continue;
        visited.insert(cur);
        res += to_string(i);
        helper(n, k, total, visited, res);
    }
}
string crackSafe(int n, int k) { // time: O(k^(n + 1)); space: O(k^n)
    string res = string(n, '0');
    unordered_set<string> visited({res});
    helper(n, k, pow(k, n), visited, res);
    return res;
}
```
