# Permutations II

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

Example:

``````Input:
[1,1,2]

Output:

[
[1,1,2],
[1,2,1],
[2,1,1]
]``````

## Analysis

``if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;``

``if(i>0 &&nums[i-1]==nums[i] && used[i-1]) continue;``

``````while (i < nums.length - 1 && nums[i + 1] == nums[i]){
i++;
}``````

## Solution

Backtracking - 1

``````class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
permuteHelper(nums, used, new LinkedList<Integer>(), ans);

return ans;
}

private void permuteHelper(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
if (path.size() == nums.length) {
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}

used[i] = true;
permuteHelper(nums, used, path, ans);
path.remove(path.size() - 1);
used[i] = false;
}
}
}``````

Backtracking - 2

``````class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
permuteHelper(nums, used, new LinkedList<Integer>(), ans);

return ans;
}

private void permuteHelper(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
if (path.size() == nums.length) {
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}

used[i] = true;
permuteHelper(nums, used, path, ans);
path.remove(path.size() - 1);
used[i] = false;
while (i < nums.length - 1 && nums[i + 1] == nums[i]){
i++;
}
}
}
}``````

Backtracking - Swap

https://leetcode.com/problems/permutations-ii/discuss/18648/Share-my-Java-code-with-detailed-explanantion

``````class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if(nums == null || nums.length == 0){
return ans;
}
helper(ans, nums, 0);
return ans;
}

private void helper(List<List<Integer>> ans, int[] nums, int start){
if(start == nums.length){
return;
}

for(int i=start;i<nums.length;i++){
if(!containsDuplicates(nums, start, i)){
swap(nums, start, i);
helper(ans, nums, start+1);
swap(nums, start, i);
}
}
}

private boolean containsDuplicates(int[] nums, int start, int i){
for(int j=start;j<i;j++){
if(nums[j] == nums[i]){
return true;
}
}
return false;
}

private List<Integer> convertToList(int[] nums){
List<Integer> item = new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){