# 0047. 全排列 II

## 题目地址(47. 全排列 II)

<https://leetcode-cn.com/problems/permutations-ii/>

## 题目描述

```
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
```

## 前置知识

* [回溯](https://github.com/azl397985856/leetcode/blob/master/thinkings/backtrack.md)

## 公司

* 阿里
* 腾讯
* 百度
* 字节

## 思路

回溯的基本思路清参考上方的回溯专题。

这道题和第 46 题不一样的点在于其有重复元素。比如题目给的 \[1,1,2]。

如果按照 46 题的解法，那么就会有重复的排列。 回顾一下 46 题我们的逻辑。以 \[1,1,2] 为例，我们的逻辑是：

* 先从 \[1,1,2] 选取一个数。
* 然后继续从 \[1,1,2] 选取一个数，并且这个数不能是已经选取过的数。
* 重复这个过程直到选取的数字达到了 3。

如果继续沿用上面的逻辑，那么我们是永远无法拿到全部三个数字的，因此我们的逻辑需要变化。

这里我的算法是记录每一个被选取的索引，而不是值，这就保证了**同一个数字不会被选取多次，并且可以选取所有数字了**。

不过这还是有一个问题。 仍然以 \[1,1,2] 为例，如果第一次选取了第一个 1，第二次选取了第二个 1，这就产生了一个组合 \[1,1,2]。 如果继续第一次选取了第二个 1，而第二次选取了第一个 1，那么又会产生组合 \[1,1,2]，可以看出这两个组合是重复的。（题目认为这两种情况应该算一种）

一个解决方案是对 nums 进行一次排序，并规定如果 **i > 0 and nums\[i] == nums\[i - 1] and visited\[i - 1]**， 则不进行选取即可。

经过这样的处理，每次实际上都是从后往前依次重复的数。仍然以上面的 \[1,1,2] 为例。\[1,1,2] 这个排列一定是先取的第二个 1，再取第一个 1，最后取的 2。这样可以避免重复的原因在于：如果先取的第一个 1，那么永远无法取到三个数，便形成了一个不可行解。

## 关键点解析

* 回溯法
* backtrack 解题公式

## 代码

* 语言支持: Javascript，Python3, CPP

JS Code:

```javascript
/*
 * @lc app=leetcode id=47 lang=javascript
 *
 * [47] Permutations II
 */
function backtrack(list, nums, tempList, visited) {
  if (tempList.length === nums.length) return list.push([...tempList]);
  for (let i = 0; i < nums.length; i++) {
    // 和46.permutations的区别是这道题的nums是可以重复的
    // 我们需要过滤这种情况
    if (visited[i]) continue; // 同一个数字不能用两次
    if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) continue; // 同样值的数字不能用两次

    visited[i] = true;
    tempList.push(nums[i]);
    backtrack(list, nums, tempList, visited);
    visited[i] = false;
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const list = [];
  backtrack(
    list,
    nums.sort((a, b) => a - b),
    [],
    []
  );
  return list;
};
```

Python3 code:

```python
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """与46题一样，当然也可以直接调用itertools的函数，然后去重"""
        return list(set(itertools.permutations(nums)))

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """自己写回溯法，与46题相比，需要去重"""
        # 排序是为了方便去重
        nums.sort()
        res = []
        def backtrack(nums, pre_list):
            if len(nums) <= 0:
                res.append(pre_list)
            else:
                for i in range(len(nums)):
                    # 同样值的数字只能使用一次
                    if i > 0 and nums[i] == nums[i-1]:
                        continue
                    p_list = pre_list.copy()
                    p_list.append(nums[i])
                    left_nums = nums.copy()
                    left_nums.pop(i)
                    backtrack(left_nums, p_list)
        backtrack(nums, [])
        return res
```

CPP Code:

```cpp
class Solution {
private:
  vector<vector<int>> ans;
  void permute(vector<int> nums, int start) {
    if (start == nums.size() - 1) {
      ans.push_back(nums);
      return;
    }
    for (int i = start; i < nums.size(); ++i) {
      if (i != start && nums[i] == nums[start]) continue;
      swap(nums[i], nums[start]);
      permute(nums, start + 1);
    }
  }
public:
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    permute(nums, 0);
    return ans;
  }
};
```

## 相关题目

* [31.next-permutation](/leetcode-solution/medium/31.next-permutation.md)
* [39.combination-sum](/leetcode-solution/medium/39.combination-sum.md)
* [40.combination-sum-ii](/leetcode-solution/medium/40.combination-sum-ii.md)
* [46.permutations](/leetcode-solution/medium/46.permutations.md)
* [60.permutation-sequence](/leetcode-solution/medium/60.permutation-sequence.md)
* [78.subsets](/leetcode-solution/medium/78.subsets.md)
* [90.subsets-ii](/leetcode-solution/medium/90.subsets-ii.md)
* [113.path-sum-ii](/leetcode-solution/medium/113.path-sum-ii.md)
* [131.palindrome-partitioning](/leetcode-solution/medium/131.palindrome-partitioning.md)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/47.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.