Swift solution - Backtracking


  • 0
    class Solution {
        func countArrangement(_ N: Int) -> Int {
            if N == 0 {
                return 0
            }
            
            var visited = [Bool](repeatElement(false, count: N + 1))
            var result = 0
            
            backtracking(N, 1, &visited, &result)
            
            return result
        }
        
        private func backtracking(_ N: Int, _ pos: Int, _ visited: inout [Bool], _ result: inout Int) {
            if pos > N {
                result += 1
                return
            }
            
            for i in 1...N {
                if !visited[i] && (i % pos == 0 || pos % i == 0) {
                    visited[i] = true
                    backtracking(N, pos + 1, &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.