LeetCode 47. 全排列 II

[Chocolate1999]

仰望星空的人，不应该被嘲笑

题目描述

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

本题是求全排列，并且排列不能重复。我们用一个 vis数组维护一下，让每一条路线保证不重复选取元素，而对于每一层而言，需要判断相邻元素是否相同，相同的就没必要走了，例如下图中红色三角形部分。

果当前的选项 nums[i] ，与同一层的上一个选项 nums[i - 1] 相同，且 nums[i - 1]有意义（即索引 >= 0），且没有被使用过，那就跳过该选项。

因为 nums[i - 1]如果被使用过，它会被修剪掉，不是一个选项了，即便它和 nums[i]重复，nums[i]还是可以选的。

参考xiao_ben_zhu大佬题解

var permuteUnique = function(nums) {
    let res = [];
    nums.sort((a,b) => a-b);
    let vis = {};
    let dfs = (t) => {
      if(t.length === nums.length){
        res.push(t);
      }
      for(let i=0;i<nums.length;i++){
        if(i-1>=0 && nums[i] == nums[i-1] && !vis[i-1]) continue;
        if(vis[i]) continue;
        vis[i] = true;
        t.push(nums[i]);
        dfs(t.slice(),i+1);
        t.pop();
        vis[i] = false;
      }
    }
    dfs([],0);
    return res;
};

最后

文章产出不易，还望各位小伙伴们支持一波！

往期精选：

小狮子前端の笔记仓库

访问超逸の博客，方便小伙伴阅读玩耍~

学如逆水行舟，不进则退

[Chocolate1999]

二刷

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    let res = [];
    let vis = {};
    nums.sort((a, b) => a - b);
    let dfs = (t) => {
        if (t.length == nums.length) {
            res.push(t);
        }
        for (let i = 0; i < nums.length; i++) {
            if (nums[i - 1] == nums[i] && i - 1 >= 0 && !vis[i - 1]) continue;
            if (vis[i]) continue;
            vis[i] = true;
            t.push(nums[i]);
            dfs(t.slice());
            t.pop();
            vis[i] = false;
        }
    }
    dfs([]);
    return res;
};