Print all possible permutations of an Array 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.

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

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".

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