Last Updated: 15 Jan, 2021

All Unique Permutations

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now