47. 全排列 II

解题思路

• 这个题目的特点在于给定的序列是可包含重复数字的，要求我们返回所有不重复的全排列。
• 遇到需要去重，通用的解题套路就是先排序，这样相等的元素相邻才能方便比较去重
• 大家可以看《46. 全排列》的题解回溯算法的通用解题套路：在递归之前做选择，在递归之后撤销刚才的选择 当前实现的代码中只增加了一句代码实现去重

if (nums[i] == nums[i - 1] && !visited[i - 1]) continue;

• 回溯算法的思路是这样的：举例来说，nums = [1,1,2]，选择了第 0 个 1，因为有 visited 来判断是否是否已经选择过了，所以后面的选择中，第 0 个 1 是不能再选择了；
• 那去重的逻辑是比方说我只有选择了第 0 个 1，才能选择第 1 个 1，或者换句话说如果我第 0 个 1 没有选择，那第 1 个 1 也不能选择才能保证排列中没有重复的

代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  nums.sort((a, b) => a - b)
  let len = nums.length,
    result = [],
    visited = new Array(len).fill(false)

  const dfs = (depth, path, visited) => {
    // 遍历到叶子结点了，可以返回了
    if (depth === len) {
      result.push([...path])
    }

    for (let i = 0; i < len; i++) {
      if (nums[i] == nums[i - 1] && !visited[i - 1]) continue
      // 如果没遍历过
      if (!visited[i]) {
        // 压入 path 数组，然后是否遍历过的数组此下标处变为 true
        path.push(nums[i])
        visited[i] = true
        // 继续 dfs，直到最后一层
        dfs(depth + 1, path, visited)
        // 进行回溯，还原，以便下一次使用
        visited[i] = false
        path.pop()
      }
    }
  }

  dfs(0, [], visited)
  return result
}