Print all possible permutations of an Array in O(1) space

Posted by N.K. Chauhan on Sep 28, 2022

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

Related


Two Sum - return index of a pair of array elements with a given sum

Rain water trapping problem - O(n) time & O(n) space

Find a triplet in an array that sums to a given number

Program to print Intersection of two sorted arrays

Program to print Union of two sorted arrays

Count the number of inversions in an array - in O(n log n) time

Word Break Problem (Using HashMap and DP)

Longest substring without repeating characters

Print all Subsets (Power Set) of a given array

Merge two sorted arrays in O(1) space