Leetcode #753: Cracking the Safe

import Foundation

class Solution {
    func crackSafe(_ n: Int, _ k: Int) -> String {
        var totalSize = Int(pow(Double(k),Double(n)))
        var str = ""
        for _ in 0..<n {
            str += "0"
        }
        var visited: Set<String> = [str]
        if dfs(&str, totalSize, n, k, &visited) {
            return str
        }
        return ""
    }
    
    private func dfs(_ str: inout String, _ totalSize: Int, _ n: Int, _ k: Int, _ visited: inout Set<String>) -> Bool {
        if visited.count == totalSize {
            return true
        }
        for i in stride(from: 0, to: k, by: 1) {
            var tmp = String(str.suffix(n-1)) + String(i)
            if !visited.contains(tmp) {
                str += String(i)
                visited.insert(tmp)
                if dfs(&str, totalSize, n, k, &visited) {
                    return true
                }
                str = String(str.dropLast())
                visited.remove(tmp)
            }
        }
        return false
    }
}