Array Permutation

Perm

	// vim: syntax=swift
extension Array {
    func chopped() -> (Element, [Element])? {
        guard let x = self.first else { return nil }
        return (x, Array(self.suffix(from: 1)))
    }
}
extension Array {
    func interleaved(_ element: Element) -> [[Element]] {
        guard let (head, rest) = self.chopped() else { return [[element]] }
        return [[element] + self] + rest.interleaved(element).map { [head] + $0 }
    }
}
extension Array {
    var permutations: [[Element]] {
        guard let (head, rest) = self.chopped() else { return [[]] }
        return rest.permutations.flatMap { $0.interleaved(head) }
    }
}
//OR
func permute(_ nums: [Int]) -> [[Int]] {
            var output: [[Int]] = []
    var numsDupe = nums
    let n  = nums.count
    backtrack(n: n, nums: &numsDupe, output: &output, first: 0)
    return output

    }
    
    func backtrack(n: Int, nums: inout [Int], output: inout [[Int]], first: Int) {
    if (first == n) { output.append(nums) }
    var i = first
    while (i < n) {
        nums.swapAt(first, i)
        backtrack(n: n, nums: &nums, output: &output, first: first + 1);
        nums.swapAt(first, i)
        i += 1
    }
}