Cracking the Safe Solution in C++

Explore More Solutions

Problem Description

Welcome to the world of “Cracking the Safe,” where your mission, should you choose to accept it, is to unlock a safe with a combination that consists of a series of digits. Imagine you’re a master thief (or just a really curious person) trying to break into a safe that only accepts combinations made up of n digits, each ranging from 0 to k-1.

Now, if you think this is as easy as pie, think again! The catch is that you need to find a combination that includes every possible sequence of n digits at least once. It’s like trying to find every possible flavor of ice cream at a new shop, but you can only take one scoop at a time. Good luck with that!

Code Solution


class Solution {
 public:
  string crackSafe(int n, int k) {
    string ans(n, '0');
    dfs(pow(k, n), n, k, {ans}, ans);
    return ans;
  }

 private:
  bool dfs(int passwordSize, int n, int k, unordered_set&& seen,
           string& path) {
    if (seen.size() == passwordSize)
      return true;

    string prefix = path.substr(path.length() - n + 1);

    for (char c = '0'; c < '0' + k; ++c) {
      prefix.push_back(c);
      if (!seen.contains(prefix)) {
        seen.insert(prefix);
        path.push_back(c);
        if (dfs(passwordSize, n, k, std::move(seen), path))
          return true;
        path.pop_back();
        seen.erase(prefix);
      }
      prefix.pop_back();
    }

    return false;
  }
};

Approach

The approach used in this solution is a depth-first search (DFS) algorithm. The idea is to explore all possible combinations of digits while keeping track of the sequences that have already been seen. The algorithm builds the combination step by step, ensuring that every possible sequence of n digits is included. If a sequence is not found, it backtracks and tries a different path. It’s like trying to find your way out of a maze, but instead of walls, you have digits!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(kⁿ)
Space Complexity	O(kⁿ)

Real-World Example

Imagine you’re at a high-security vault, and you need to enter a code that consists of a series of numbers. Each time you enter a number, it records the last n digits you’ve entered. To unlock the vault, you need to ensure that every possible combination of those digits has been entered at least once. This is exactly what the "Cracking the Safe" problem is about!