Given an array **arr[]** of length **n**, it contains distinct integers.

The task is to return all the possible **permutations** (in any order).

**Input:** arr = {0,1}

**Output:** [[0, 1], [1, 0]]

**Input:** arr[] = {1, 2, 3}

**Output:** [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

An array of length n has **n!** permutations.

## Solutions

### Method 1: In O(1) space

With this approach, we can print all possible permutations without using any extra space.

The idea is to start from the left element (i=0) and replace all elements from **i to n-1** with **i** one by one, passing the resulting array to the recursive call.

We have no choice but to replace the **i-th** element with itself once it is the last element, so print the array.

**Note:** After making the recursive call, the swapped elements are reverted. This is to avoid using any extra space to serve a copy.

##### Complexity

The time complexity of this solution is **O(n * !n)** and space complexity is **O(1)**.

### Method 2: Using extra space

If we want to generate permutations for **n** elements, then we are free to choose any element from **0 to n-1 **as the first element, so there will be **n-1** choices.

The idea is to keep track of these choices in an **auxiliary array (boolean[] taken) **of length **n**, with each index representing whether the element at** i-th** index is taken or not.

In each recur, we will check the **taken []** array and, if an element is not already taken, we will consider it as a choice.

Once choices are exhausted (n-1 elements are filled), we **print** that permutation.

**Note:** The extra space taken by **"boolean[] t"** and **"List p"** to hold copies can be avoided if, after making the recursive call, we revert changes made to "taken" and "perm".

##### Complexity

The time complexity of this solution is **O(n * !n)** and space complexity is **O(n^2)**.