All Unique Permutations

Easy

0/40

Average time to solve is 15m

Contributed by

20 upvotes

Asked in companies

Problem statement

You are given an array Arr consisting of N integers. Your task is to find all the unique permutations of the given array. For e.g if the array is {1, 1, 2}, the unique permutations of this array are {1, 1, 2}, {1, 2, 1}, {2, 1, 1}. Note that the total number of permutations of {1,1,2} is equal to 6 but out of those {1,1,2} and {1,2,1} occur twice.

Note:

1. There might be duplicates present in the array.
2. The order of the permutations in the output does not matter.
3. Do not use any kind of in-built library functions to find the answer.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains the integer N, denoting the size of the array.

The second line contains N space-separated integers denoting the array elements.

Output Format:

The output contains K lines, where each line contains N space-separated integers denoting one of the unique permutations of the given array.

Output for each test case must be in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= N <= 6

Time Limit: 1 sec

Sample Input 1:

3
1 1 2

Sample Output 1:

1 1 2
1 2 1
2 1 1

Explanation for Sample Input 1:

The three unique permutations are  {1, 1, 2}, {1, 2, 1}, {2, 1, 1}. Note that {1, 2, 1}, {2, 1, 1} {1, 1, 2} is also acceptable answer.

Sample Input 2:

3
1 2 3

Sample Output 2:

Explanation for Sample Input 2:

The six unique permutations are  {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}. Note that the order of permutations does not matter, you can return them in any order.

Hint 1

Try the simplest possible way.

Approaches (1)

Approach 1

Backtracking

Since we can not manually find the permutations, the best approach is to solve this problem by backtracking.
So for solving the problem by backtracking, let us have a recursive function generatePerm() which will generate all the permutations of the array.
Since we do not want to generate the same permutations again and again, we can use a map of vectors and int to check whether we have already generated a permutation or not. Let the map name be isGenerated.
Let 'CURR' be the array which will store the current permutation that we are working with. If the size of current is ‘N’, that means we have successfully generated a permutation and we can print it.
Let ‘i’ = 0 initially, which points to the current element of the array
Now for all ‘j’ = ‘i’ to ‘N’ - 1, do the following:
- Push ‘ARR[i]’ into ‘CURR’.
- Swap(‘ARR[i]’ , ‘ARR[j]’) to generate new permutation.
- Call generatePerm() from ‘i’ + 1.
- Pop the last element from 'CURR'.
After the end of this loop, we will have all the unique permutations of the array.

Time Complexity

O(N * N!), where N is the number of elements in the array.

Space Complexity

O(N * N!), where N is the number of elements in the array.

(100% EXP penalty)

All Unique Permutations

Console