**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]:**

- better space: do swap in-place without extra solution array
- 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])
}
}
}
```