# ac solution code

• 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
}
}
``````

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