<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>

class Solution {
public:
    string str(int x){
        char c = '0'+x;
        string s = "";
        s = s+c;
        return s;
    }
    void generate(vector<string>&gen,string s,int i,int k,int n){
        if(i==n){
            gen.push_back(s);
            return;
        }
        for(int idx=0;idx<k;idx++){
            string dedo = s;
            generate(gen,s.append(str(idx)),i+1,k,n);
            s = dedo;
        }
    }

    void dfs(int node,vector<int>&vis,vector<int>adj[],stack<int>&order){
        vis[node]=1;
        for(auto j:adj[node]){
            if(vis[j]) continue;
            dfs(j,vis,adj,order);
        }
        order.push(node);
    }
    string crackSafe(int n, int k) {
        vector<string> gen;
        generate(gen,"",0,k,n);
        map<string,int> mp;
        for(int i=0;i<gen.size();i++){
            mp[gen[i]]=i;
        }
        vector<int> adj[gen.size()];
        for(auto s:gen){
            string subs;
            if(n==1) subs="";
            else subs = s.substr(1,n-1);
            string dedo = subs;
            cout<<s<<endl;
            for(int i=0;i<k;i++){
                string second = subs+str(i);
                // cout<<second<<endl;
                if(second==s) continue;
                adj[mp[s]].push_back(mp[second]);
                // cout<<s<<" "<<subs<<endl;
            }
            cout<<"Finish"<<endl;
        }
        stack<int> order;
        vector<int> vis(gen.size(),0);
        dfs(0,vis,adj,order);
        // cout<<gen[1]<<endl;
        int firstt = order.top();
        order.pop();
        string ans = gen[firstt];
        while(!order.empty()){
            int node = order.top();
            order.pop();
            ans.append(gen[node].substr(n-1,1));
        }
        return ans;
    }
};
17700