# 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

这一题接Permutations，用常规模板，要注意的是duplicate的处理。有重复元素时，通常会先sort，这样处理起来比较方便，因为sort后，重复元素会具有连续的index。

LeetCode上有一个很有意思的讨论帖：<https://leetcode.com/problems/permutations-ii/discuss/18594/Really-easy-Java-solution-much-easier-than-the-solutions-with-very-high-vote>

就是在于当判断出现重复元素时，如何处理。帖主给出的是：

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

但是人们发现以下同样可以work：

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

其实区别就在于是出现重复元素的时候，是用第一个还是最后一个。帖主的方法更优化。

简单一点的理解就是因为在循环中，如果nums\[i - 1]用过了，那么在backtracking的时候其实是会把used\[i - 1]重新设成false的，used\[ i - 1]为false，其实是说明nums\[ i - 1]在i - 1的时候被使用过了。

另外还有一个更好的方式，直接增加一个内层循环，跑出连续的重复元素:

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

## Solution

Backtracking - 1

```java
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) {
            ans.add(new LinkedList<>(path));
            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;
            }

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

Backtracking - 2

相比Permutations，只是在permuteHelper的for-loop里面最后增加了一段，来skip掉重复的元素

```java
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) {
            ans.add(new LinkedList<>(path));
            return;
        }

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

            path.add(nums[i]);
            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>

```java
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){
            ans.add(convertToList(nums));
            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++){
            item.add(nums[i]);
        }
        return item;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/backtracking/permutations-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.