[Leetcode] Permutations I and II

Problem

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Duplicate
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].

Algorithm

Consider the first digit of the array, it can be swapped with any other digits, including itself to generate new permutations. After determining the first digit, we can recursively permute the remaining n-1 digits. 

If the input collection has duplicates, we need to avoid duplicated permutations. Follow this rule:

                  "Whenever place a number, make sure it is not placed at this location before. "

Therefore, we use a set to record the visited numbers at this location. If it is not visited before, we place it. Otherwise, skip this number.

Note, sort the array then skip the duplicates seems not work. Since when swapping the numbers, the order of the array is destroyed. Therefore, we cannot avoid duplicates correctly in this way. 

Code