# Question

Formatted question description: https://leetcode.ca/all/47.html

47 Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

@tag-backtracking



# Algorithm

Due to the possibility of repeated numbers in the input array, if you follow the previous algorithm, there will be repeated permutations. We need to avoid repetition. In the recursive function, we must determine whether the previous number is equal to the current number. If it is equal, and its The value in the corresponding visited is 1, the current number can be used (the reason for this will be explained below), otherwise it needs to be skipped, so that no duplication will occur.

### Note

1 .use the idea of insertion sort: Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration.

2 . to skip duplicates, two ways: 1. act on permutation_I result, use a set to filter duplicated results: bulky and extra o(N) operations and o(N) space 2. truncate during iteration or recursion, but: need sort nums[] array first, extra o(NlogN) operations

Java