ac solution code


  • 0

    The basic idea is using DFS to pick up one unvisited element from the array to append to the position current.size() of 'current' array.

    To ignore duplicates: we don't put the same element to the same position

    DFS - time = O(n!), space = O(2n) = O(n)

    For position i, there're (n-i) possible numbers to put if no duplicates. So it's (n-0)(n-1)(n-2)..(n-(n-1)) = n!

    Solution1. Minor improvement when check duplicates

        func permuteUnique(_ nums: [Int]) -> [[Int]] {
            var res = [[Int]]()
            var solution = [Int]()
            var visited = [Bool](repeating: false, count: nums.count)
            // sort nums first
            let nums = nums.sorted(by: <)
            DFS(nums, &res, &solution, &visited)
            return res
        }
    
        private func DFS(_ nums: [Int], _ res:inout [[Int]], _ solution:inout [Int], _ visited:inout[Bool]) {
            // termination case
            if solution.count == nums.count {
                res.append(solution)
                return
            }
    
            /* Loop all nums and append unvisited one to solution */
            // Permutation basic definition: n(n-1)(n-2)..(n-m)
            // On mth step, select from n-m numbers. (check all n numbers, exclude selected m numbers in list)
            // time: O(n!)
            for i in 0..<nums.count {
                // If same as the prevous one, only if the prevous one is used, otherwise ignore
                if visited[i] || (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1]) {
                    continue
                }
                solution.append(nums[i])
                visited[i] = true
                DFS(nums, &res, &solution, &visited)
                visited[i] = false
                solution.removeLast()
            }
        }
    

    Solution2.

    func permuteUnique(_ nums: [Int]) -> [[Int]] {
            var ret = [[Int]]()
            var solution = [Int]()
            var visited = Array(repeating: false, count: nums.count)
            var numsCopy = [Int](nums)
            // sort nums first
            numsCopy.sort()
            DFS(numsCopy, &ret, &solution, &visited)
            return ret
        }
    
        // Pick up one unvisited element from the array to append to the position current.size() of 'current' array
        func DFS(_ nums: [Int], _ ret:inout [[Int]], _ solution:inout [Int], _ visited:inout[Bool]) {
            if solution.count == nums.count {
                ret.append(solution)
                return
            }
    
            // Permutation basic definition: n(n-1)(n-2)..(n-m)
            // On mth step, select from n-m numbers. (check all n numbers, exclude selected m numbers in list)
            // time: O(n!)
            var i = 0
            while i < nums.count {
                if !visited[i] {
                    solution.append(nums[i])
                    visited[i] = true
                    DFS(nums, &ret, &solution, &visited)
                    visited[i] = false
                    solution.removeLast()
    
                    // Ignore duplicates: we don't put the same element to the same position
                    while i + 1 < nums.count, nums[i + 1] == nums[i] {
                        i += 1
                    }
                }
                i += 1
            }
        }
    

Log in to reply
 

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