class Solution {
public:
string crackSafe(int a, int b) {
const int d = pow(b, a) + a - 1;
string f(a, '0');
unordered_set<string> e{f};
if (dfs(f, d, a, b, e))
return f;
return "";
}
private:
bool dfs(string& f, const int d, const int a, const int b, unordered_set<string>& e) {
if (f.length() == d)
return true;
string node = f.substr(f.length() - a + 1, a - 1);
for (char c = '0'; c < '0' + b; ++c) {
node.push_back(c);
if (!e.count(node)) {
f.push_back(c);
e.insert(node);
if (dfs(f, d, a, b, e)) return true;
e.erase(node);
f.pop_back();
}
node.pop_back();
}
return false;
}
};