> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/hui-su/47-quan-pai-lie-ii.md).

# \[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
```