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
Complexity
The time complexity of this solution is O(n * !n) and space complexity is O(n^2).