# \[47]\[中等]\[回溯] 全排列 II

## 题目描述

[47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/)

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

```
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
```

示例 2：

```
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```

提示：

* 1 <= nums.length <= 8
* -10 <= nums\[i] <= 10

## 解题思路

由于数组中有重复数字, 因此不能再像[\[46\]\[中等\]\[回溯\] 全排列](/garnet/suan-fa/hui-su/46-quan-pai-lie.md)一样, 而是需要考虑重复情况的剪枝问题.

在列举结果列表第i个位置时, 如果有多个一样的候选值, 那么只考虑其中一个就可以, 考虑其他几个得到的结果也是一样的, 因此可以剪枝.

在每一层使用一个单独的哈希表来记录本层中哪些值被搜索过, 迭代过程中遇到本层中搜索过的值, 就可以剪枝跳过了.

```python
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(path, residual):
            if len(residual) == 0:
                results.append(path[:])

            seen = set()
            for i, num in enumerate(residual):
                if num not in seen:
                    seen.add(num)
                    path.append(num)
                    dfs(path, residual[:i] + residual[i + 1:])
                    path.pop()

        results = []
        dfs([], nums)
        return results
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/hui-su/47-quan-pai-lie-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.