【亡羊补牢】挑战数据结构与算法第23期 LeetCode 47. 全排列 II（递归与回溯）

84 阅读 0 评论 56 点赞

我是靠谱客的博主爱撒娇哈密瓜，最近开发中收集的这篇文章主要介绍【亡羊补牢】挑战数据结构与算法第23期 LeetCode 47. 全排列 II（递归与回溯），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

题目描述

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

示例:

输入: [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;
};