Swift solution - iterative, Backtracking


  • 0
    class Solution {
        func getPermutation_Iterative(_ n: Int, _ k: Int) -> String {
            var characters = [Character]()
            var visited = [Bool](repeatElement(false, count: n))
            var k = k
            var factor = 1
            
            k -= 1
            for i in 1..<n {
                factor *= i
            }
            for i in 0..<n {
                var index = k / factor
                k %= factor
                for j in 0..<n {
                    if !visited[j] {
                        if index == 0 {
                            visited[j] = true
                            characters.append(Character(UnicodeScalar("0".asciiValueOfCharacter + j + 1)!))
                            break
                        } else {
                            index -= 1
                        }
                    }
                }
                if i < n - 1 {
                    factor /= (n - 1 - i)
                }
            }
            
            return String(characters)
        }
        
        func getPermutation(_ n: Int, _ k: Int) -> String {
            var result = ""
            var visited = [Bool](repeatElement(false, count: 10))
            var count = 0
            
            backtracking(0, n, k, [Character](), &count, &visited, &result)
            
            return result
        }
        
        private func backtracking(_ pos: Int, _ n: Int, _ k: Int, _ characters: [Character], _ count: inout Int, _ visited: inout [Bool], _ result: inout String) {
            if pos == n {
                count += 1
                if count == k {
                    result = String(characters)
                    return
                }
            }
            
            for i in 1...n {
                if !visited[i] {
                    visited[i] = true
                    let character = Character(UnicodeScalar("0".asciiValueOfCharacter + i)!)
                    backtracking(pos + 1, n, k, characters + [character], &count, &visited, &result)
                    visited[i] = false
                }
            }
        }
    }
    

Log in to reply
 

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