<p>There is a safe protected by a password. The password is a sequence of <code>n</code> digits where each digit can be in the range <code>[0, k - 1]</code>.</p>

<p>The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the <strong>most recent </strong><code>n</code><strong> digits</strong> that were entered each time you type a digit.</p>

<ul>
	<li>For example, the correct password is <code>&quot;345&quot;</code> and you enter in <code>&quot;012345&quot;</code>:

	<ul>
		<li>After typing <code>0</code>, the most recent <code>3</code> digits is <code>&quot;0&quot;</code>, which is incorrect.</li>
		<li>After typing <code>1</code>, the most recent <code>3</code> digits is <code>&quot;01&quot;</code>, which is incorrect.</li>
		<li>After typing <code>2</code>, the most recent <code>3</code> digits is <code>&quot;012&quot;</code>, which is incorrect.</li>
		<li>After typing <code>3</code>, the most recent <code>3</code> digits is <code>&quot;123&quot;</code>, which is incorrect.</li>
		<li>After typing <code>4</code>, the most recent <code>3</code> digits is <code>&quot;234&quot;</code>, which is incorrect.</li>
		<li>After typing <code>5</code>, the most recent <code>3</code> digits is <code>&quot;345&quot;</code>, which is correct and the safe unlocks.</li>
	</ul>
	</li>
</ul>

<p>Return <em>any string of <strong>minimum length</strong> that will unlock the safe <strong>at some point</strong> of entering it</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1, k = 2
<strong>Output:</strong> &quot;10&quot;
<strong>Explanation:</strong> The password is a single digit, so enter each digit. &quot;01&quot; would also unlock the safe.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, k = 2
<strong>Output:</strong> &quot;01100&quot;
<strong>Explanation:</strong> For each possible password:
- &quot;00&quot; is typed in starting from the 4<sup>th</sup> digit.
- &quot;01&quot; is typed in starting from the 1<sup>st</sup> digit.
- &quot;10&quot; is typed in starting from the 3<sup>rd</sup> digit.
- &quot;11&quot; is typed in starting from the 2<sup>nd</sup> digit.
Thus &quot;01100&quot; will unlock the safe. &quot;10011&quot;, and &quot;11001&quot; would also unlock the safe.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 4</code></li>
	<li><code>1 &lt;= k &lt;= 10</code></li>
	<li><code>1 &lt;= k<sup>n</sup> &lt;= 4096</code></li>
</ul>

const int N = 4, K = 11, MAX = 4100;
vector<int> adj[MAX];
int vis[MAX];
int n, k, tot;
string full;
bool found;

int btoi(const string &s){
    int res = 0, sz = s.size(), f = 1;
    
    while(sz--){
        int v = s[sz] - '0';
        res += v*f;
        f *= k;
    }
    return res;
}

void to_base(int v, string &res){
    
    while(v>0){
        int rem = v%k;
        char ch = ('0' + rem);
        res += ch;
        v /= k;
    }
    while(res.size() < n) res += '0';
    reverse(res.begin(), res.end());
}

void dfs(int u, string &cur, int cnt){
    if(found) return;
    vis[u] = true;
    string bin_rep;
    to_base(u, bin_rep);
    if(cnt == tot-1){
        found = true;
        cur += bin_rep;
        full = cur;
        return;
    }

    for(int v: adj[u]){
        if(!vis[v]){
            cur += bin_rep;
            dfs(v, cur, cnt+1);
            for(int i = 0; i<n; i++) cur.pop_back();
        }
    }
    vis[u] = false;
}

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int getRandomNumber(int l, int r){
   uniform_int_distribution<int> dist(l, r);
   return dist(rnd);
}

class Solution {
public:
    string crackSafe(int nn, int kk) {
        n = nn;
        k = kk;
        for(int i = 0; i<MAX; i++) adj[i].clear(), vis[i] = false;
        full = "";
        found = false;
        tot = pow(k, n);
        
        for(int i = 0; i<tot; i++){
            string rep;
            to_base(i, rep);
            
            reverse(rep.begin(), rep.end());
            rep.pop_back();
            reverse(rep.begin(), rep.end());
            for(int j = 0; j<k; j++){
                char ch = ('0' + j);
                rep.push_back(ch);
                int v = btoi(rep);
                rep.pop_back();
                adj[i].push_back(v);
            }
        }
        string cur;
        dfs(0, cur, 0);
        string ans;
        int f = 1;
        for(int i = 0; i<full.size(); i+=f){
            ans += full[i];
            if(i >= n-1)
                f = n;
        }
        return ans;       
    }
};
11300