ac solution code


  • 0

    Solution1. time = O(n!); space = O(2n) = O(n) - path, visited
    Prefer this solution, as it can easily solve permutationsII with minor change

    The basic idea is to append nums[i] to path, mark it as visited, and keep recursion with nums - nums[i], till satisfies the termination case: get n elements in path array.
    Each step, check if nums[i] exists in path, that cost O(i) - i in 0...n-1 time, total time complexity = O(n!)

    func permute(_ nums: [Int]) -> [[Int]] {
            var res = [[Int]]()
            var path = [Int]()
            var visited = [Bool](repeating: false, count: nums.count)
            DFS(nums, &visited, &path, &res)
            return res
        }
        private func DFS(_ nums: [Int], _ visited: inout [Bool], _ path: inout [Int], _ res: inout [[Int]]) {
            if path.count == nums.count {// Termination case
                res.append(path)
                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!)
            for i in 0 ..< nums.count {
                if visited[i] {
                    continue
                }
                path.append(nums[i])
                visited[i] = true
                DFS(nums, &visited, &path, &res)
                // Recover
                visited[i] = false
                path.removeLast()
            }
        }
    

    Solution2. time = O(n!), space = O(1) - in-place (actually O(n) to copy nums)

    Permutations of A[1..n] equals to:
    A[1] + permutation of (A[1..n] - A[1])
    A[2] + permutation of (A[1..n] - A[2])
    ...
    A[n] + permutation of (A[1..n] - A[n])

    Put A[i] at the first place, and keep permutations of A-A[i]:

    1. better space: do swap in-place without extra solution array
    2. better time: as the next recursion starts from begin, save the time of checking (begin-1) elements
    func permute2(_ nums: [Int]) -> [[Int]] {
            var res = [[Int]]()
            var nums = nums
            DFS2(&nums, &res, 0)
            return res
        }
        private func DFS2(_ nums: inout [Int], _ res: inout [[Int]], _ start: Int) {
            if start == nums.count {
                res.append(nums)
                return
            }
            for i in start ..< nums.count {
                if i != start {
                    swap(&nums[i], &nums[start])
                }
                DFS2(&nums, &res, start + 1)
                if i != start {// Recover nums
                    swap(&nums[start], &nums[i])
                }
            }
        }
    
    

Log in to reply
 

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