# Backtracking - Permutations II

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Medium

DFS, Backtracking, Map

## Problem

Given a collection of numbers, `nums`

, that might contain duplicates, return *all possible unique permutations in any order.*

**Example 1:**

1
2
3
4
5

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]

**Example 2:**

1
2

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

## Solution

This is very similar to the previous Permutations problem however like we used almost the same solution for Subset II from Subset, we won’t be able to do the same. Here in order to avoid the duplicates, we will transform the input `list`

to a `map`

object and use that to traverse the `dfs()`

for negating sequences.

1
2
3

nums_map=collections.defaultdict(int)
for n in nums:
nums_map[n]+=1

1
2
3
4

{
1: 2,
2: 1
}

In the `dfs()`

function, the terminating/base condition is similar to what we have used in the Subset problem. Like in the Subset problem we will define `permutation_arr`

outside, though it can also be passed as an argument in the `dfs()`

function.

1
2
3
4
5
6

permutation_arr = []
output=[]
def dfs():
if len(permutation_arr) == len(nums):
output.append(permutation_arr.copy())
return

Now we will loop through each unique element in the `nums_map`

. If the number in the `nums_map`

is more than `0`

then we know we can call `dfs()`

again. The idea is to keep subtracting the value from the `nums_map`

however the loop will only be for `len(nums_map.keys())`

. This will ensure number of unique combinations are equal to number of unique elements in the input `nums`

array.

1
2
3

for key in nums_map:
if nums_map[key] >0 :
...

Now add each key to the `permutation_arr`

, decrement the counter in the `nums_map`

then run `dfs()`

. Once its completed perform the backtracking.

1
2
3
4
5
6
7
8
9

for key in nums_map:
if nums_map[key] >0 :
permutation_arr.append(key)
nums_map[key]-=1
dfs()
nums_map[key]+=1
permutation_arr.pop()

Finally invoke `dfs()`

and return the `output`

.

1
2

dfs()
return output

Here is the visualization.

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def permutations_ii(nums):
output = []
permutation_arr = []
nums_map = collections.defaultdict(int)
for n in nums:
nums_map[n] += 1
def dfs():
if len(permutation_arr) == len(nums):
output.append(permutation_arr.copy())
return
for key in nums_map:
if nums_map[key] > 0:
permutation_arr.append(key)
nums_map[key] -= 1
dfs()
nums_map[key] += 1
permutation_arr.pop()
dfs()
return output