## Algorithm

Problem Name: 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"
- "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. "01100", "10011", and "11001" would also unlock the safe.
```

Constraints:

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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
string crackSafe(int n, int k) {
int target = pow(k, n);
string res;
for (int i = 0; i  <  n; ++i) {
res += '0';
}
string cur = res;
unordered_set < string>visited;
dfs(res, target, visited, n, k, cur);
return res;
}

bool dfs(string& res, int& target, unordered_set < string>& visited, int n, int k, string cur) {
if (visited.count(cur)) {
return false;
}

visited.insert(cur);

if (visited.size() == target) {
return true;
}

string next = cur.substr(1);

for (int i = 0; i  <  k; ++i) {
next.push_back('0' + i);
if (!visited.count(next)) {
res.push_back('0' + i);
if (dfs(res, target, visited, n, k, next)) {
return true;
}
res.pop_back();
}
next.pop_back();
}
visited.erase(cur);
return false;
}
};
``````
Copy The Code &

Input

cmd
n = 1, k = 2

Output

cmd
"10"

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def crackSafe(self, n, k):
s = '0' * (n - 1)
D = '9876543210'[-k:]
for _ in range(k**n):
s += next(d for d in D if (s + d)[-n:] not in s)
return s
``````
Copy The Code &

Input

cmd
n = 1, k = 2

Output

cmd
"10"

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
public class _0753_CrackingtheSafe
{
public string CrackSafe(int n, int k)
{
var totalSize = (int)Math.Pow(k, n);
var alreadySeen = new HashSet < string>();
var results = new StringBuilder();

var start = new string('0', n - 1);
results.Append(start);

return results.ToString();
}

private void DFS(string currentString, int k, int totalSize, ISet < string> alreadySeen, StringBuilder results)
{
return;

for (int i = 0; i  <  k; i++)
{
var newString = currentString + i.ToString();
continue;

results.Append(i);
}
}
}
}
``````
Copy The Code &

Input

cmd
n = 2, k = 2

Output

cmd
"01100"