# All Unique Permutations

Posted: 15 Jan, 2021

Difficulty: Easy

#### 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
```

Approach 1

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

SIMILAR PROBLEMS

# Distinct Characters

Posted: 8 May, 2021

Difficulty: Moderate

# Maximum Height Tree

Posted: 25 Jun, 2021

Difficulty: Hard

# Postorder Traversal

Posted: 22 Jul, 2021

Difficulty: Easy

# Find All Subsets

Posted: 23 Jul, 2021

Difficulty: Easy

# Print All Subsets

Posted: 23 Jul, 2021

Difficulty: Easy