# Recursive C++ solution with lots of comments - unlike others here, I won't write that it's easy.

• ``````class Solution {
public:

//generate all combinations of words of size n with k letters
vector<string> generateCombs(int n, int k){

vector<string> result;

if(n == 1){
for(char i = '0'; i < '0' + k; ++i){
string tmp(1,i);
result.push_back(tmp);
}
}
else{
auto temp = generateCombs(n - 1,k);
for(auto p : temp){
for(char i = '0'; i < '0'+ k; ++i){
string pt = p + string(1,i);
result.push_back(pt);
}
}
}

return result;
}

//type declarations
using sbpair = pair<string,bool>;
using vsbpair = vector<sbpair>;

//a hash map that will be used during the visit
unordered_map<string,vsbpair> prefs;

//
//visit is a recursive function that attempts to find a Hamiltonian path
// betweem nodes where each node corresponds to a single n-sized word.
// An edge connects two nodes if and only if the first node's n-1th suffix corresponds
// to the second node's n - 1th prefix.
//
bool visit(sbpair &p, string &res, size_t size){

if(size == 1){
res += p.first;
return true;
}

p.second = true;
string prevRes = res;
res += p.first.substr(0,1);
string ss = p.first.substr(1);

for(auto &pr : prefs[ss]){
if(!pr.second){
if(visit(pr,res,size - 1)){
return true;
}
}
}

p.second = false;
res = prevRes;
return false;
}

string crackSafe(int n, int k) {

//get all combinations of size n with k letters
auto combs = generateCombs(n,k);

// The case of n = 1 is a special case as there are no overlapping
// prefixes and suffixes. In this case we just return a single string
// which corresponds to all the 1 letter words found.
if(n == 1){
string res=
accumulate(combs.begin(),combs.end(),string(),[](string curr,const string &s){
curr += s;
return curr;
});

return res;
}

//go through the combinations and add them to the prefs (prefixes) hashtable
for(auto &c : combs){
prefs[c.substr(0,n - 1)].push_back({c,false});
}

//pick the first word and find a hamiltonian path starting with it
auto &vpair = *(prefs.begin()->second.begin());
string result;
visit(vpair,result,combs.size());
return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.