47. 全排列 II

1. 题目描述

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

示例:

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

2. 解题思路

这个题目和46题相似，只是这到题目中的元素可能是重复的，下面以题目中给的[1，1，2]为例：

红色部分是需要剪掉的枝。这些路径上包含重复和元素和重复的结果。

首先，我们需要对数组元素进行排序，便于后面前后两个元素进行对比。其他步骤和46题完全一致。只是剪枝的判断条件不一样。

最关键的就是下面这句代码：

if(arr[i] || (i > 0 && !arr[i-1] && nums[i] === nums[i-1])) continue;

• 在每次遍历时，arr标记已使用的情况，所以如果arr[i]存在，说明已经遍历过，直接跳过；

• [1,1,2]是三次遍历的的结果，每一次遍历完后arr所有值都会为false，所以就有了!arr[i-1] && nums[i] === nums[i-1]，也就是说，比方第一次遍历了第一个1；第二次，首先遍历了第一个1，在遇到第二个1时，发现和第一个一样，就直接跳过了。

  3. 代码实现

  ```javascript /**

  • @param {number[]} nums

  • @return {number[][]} */ var permuteUnique = function(nums) { const res = [] nums = nums.sort() let arr = []

    const dfs = (path) => {

    if(path.length === nums.length){
        res.push([...path])
    }
    for(let i = 0; i < nums.length; i++){
        if(arr[i] || (i > 0 && !arr[i-1] && nums[i] === nums[i-1])) continue
        path.push(nums[i])
        arr[i] = true
        dfs(path)
        path.pop()
        arr[i] = false
    }

    } dfs([]) return res

}; ```

4. 提交结果