Permutations

Category: Recursion

Difficulty: Medium

Description

Write a function that takes in an array of unique integers and returns an array of all permutations of those integers in no particular order.

If the input array is empty, the function should return an empty array.

Sample Input

array = [1, 2, 3]

Sample Output

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Optimal Space & Time Complexity

O(nn!) time | O(nn!) space - where n is the length of the input array