Cracking the Safe

Description

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

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

• For example, the correct password is "345" and you enter in "012345":

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

Return any string of minimum length that will unlock the safe at some point of entering it.

 

Example 1:

Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.

Example 2:

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

 

Constraints:

• 1 <= n <= 4
• 1 <= k <= 10
• 1 <= kn <= 4096

Solution(javascript)

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var crackSafe = function(n, k) {
    let seen = new Set();
    let ans = [];
    
    const dfs = (node, k) => {
        for (let x = 0; x < k; ++x) {
            const nei = node + x;
            if (!seen.has(nei)) {
                seen.add(nei);
                dfs(nei.slice(1), k);
                ans.push(x);
            }
        }
    };
    
    if (n == 1 && k == 1) {
        return "0";
    }
    
    seen = new Set();
    ans = [];

    const sb = [];
    for (let i = 0; i < n-1; ++i) {
        sb.push("0");
    }
    
    const start = sb.join('');
    dfs(start, k);
    ans.push(start);
    return ans.join('');
};