# 47.Permutations II

## 1.Description(Medium)

Given a list of numbers with duplicate number in it. Find all **unique** permutations.

**Example**

For numbers`[1,2,2]`the unique permutations are:

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

## 2.Code

<http://www.cnblogs.com/grandyang/p/4359825.html>

<http://www.jiuzhang.com/solutions/permutations-ii/>

对于这道题。也是要求permutation,大体上的解题思路和Permutations是相同的，但是不同点在哪里呢？ 不同点为：

1. 这个给定的数组中可能会含有相同的数字.
2. 最后答案不接受重复相同的答案组.
3. 要先将数组排序，确保重复的元素是在一起的。
4. 除了不能加入之前出现过的元素之外，还不能加入本轮搜索中出现过的元素。

对于这两点要求，Permutations的解法是无法解决的，所以我们就要考虑怎样满足以上两个要求. 我们可以对整个input数组进行排序，在求解答案的时候，只要一个元素的permutation求出来了，在这个元素后面和这个元素相同的元素，我们完全都可以pass掉，其实这个方法在sum和combination里面已经是屡试不爽了.

解题思路: 除了加上对于重复答案的处理外，剩下思路同Permutation一模一样。

时间复杂度: O(n!)

由于输入数组有可能出现重复数字，如果按照之前的算法运算，会有重复排列产生，我们要避免重复的产生，在递归函数中要判断前面一个数和当前的数是否相等，如果相等，前面的数必须已经使用了，即对应的visited中的值为1，当前的数字才能使用，否则需要跳过，这样就不会产生重复排列了

```
public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        if(nums==null){
            return result;
        }
        if(nums.length==0){
            result.add(new ArrayList<Integer>());
            return result;
        }
        List<Integer> path=new ArrayList<Integer>();
        boolean[] visited=new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,path,result,visited);
        return result;
    }

    public void dfs(int[] nums,List<Integer> path,List<List<Integer>> result,boolean[] visited){
        if(path.size()==nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            /*
         上面的判断主要是为了去除重复元素影响。
         比如，给出一个排好序的数组，[1,2,2]，那么第一个2和第二2如果在结果中互换位置，
         我们也认为是同一种方案，所以我们强制要求相同的数字，原来排在前面的，在结果
         当中也应该排在前面，这样就保证了唯一性。所以当前面的2还没有使用的时候，就
         不应该让后面的2使用。
            */
            if(visited[i] || (i>0 && nums[i]==nums[i-1] && visited[i-1]==false)){
                continue;
            }
            visited[i]=true;
            path.add(nums[i]);
            dfs(nums,path,result,visited);
            path.remove(path.size()-1);
            visited[i]=false;           
        }
    }
```


---

# 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://junnie.gitbook.io/nine-chapter/4.depth-first-search/16.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.