每天一道leetcode(Day 51)

47. 全排列 II

题目描述

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

示例

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

解题思路

思路：回溯+剪枝

本题是在46.全排列的基础上增加了一个附加条件，需要去除重复的排列，但是数组去重比较困难，因此我们采用剪枝的方式来去重。

具体做法(在46.全排列的基础上增加一个 visited 数组用于记录 nums 数组中元素是否被访问过)：

• 首先，先要给 nums 进行排序，这样的做目的是方便剪枝；

• 其次，我们已经选择过的不需要再放进去了，visited[i]为 true 的时候代表节点已经选择过；

• 接下来，如果当前节点与他的前一个节点一样，并其他的前一个节点已经被遍历过了，那我们也就不需要了(nums[i]===nums[i-1]&&visited[i-1])。

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  let res = [],
    path = [],
    len = nums.length;
  let visited = new Array(len).fill(false);
  nums.sort((a, b) => a - b);
  function back_trace(path) {
    if (path.length === len) {
      res.push(path.slice());
      return;
    }
    for (let i = 0; i < len; i++) {
      if (visited[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) break;
      path.push(nums[i]);
      visited[i] = true;
      back_trace(path);
      path.pop();
      visited[i] = false;
    }
  }
  back_trace(path);
  return res;
};

参考

47. 全排列 II