排列问题也要去重了！

全排列 II

力扣题目链接：https://leetcode-cn.com/problems/permutations-ii

创新互联-专业网站定制、快速模板网站建设、高性价比姜堰网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式姜堰网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖姜堰地区。费用合理售后完善，10年实体公司更值得信赖。

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

示例 1：

  • 输入：nums = [1,1,2]
  • 输出：[[1,1,2], [1,2,1], [2,1,1]]

示例 2：

  • 输入：nums = [1,2,3]
  • 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

思路

如果对回溯算法基础还不了解的话，我还特意录制了一期视频：带你学透回溯算法(理论篇) 可以结合题解和视频一起看，希望对大家理解回溯算法有所帮助。

这道题目和全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。

这里又涉及到去重了。

在组合总和II 、子集II我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

还要强调的是去重一定要对元素经行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

我以示例中的 [1,1,2]为例 (为了方便举例，已经排序)抽象为一棵树，去重过程如图：

全排列II1

图中我们对同一树层，前一位(也就是nums[i-1])如果使用过，那么就进行去重。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

在46.全排列中已经详解讲解了排列问题的写法，在40.组合总和II 、90.子集II中详细讲解的去重的写法，所以这次我就不用回溯三部曲分析了，直接给出代码，如下：

C++代码

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking (vector& nums, vector& used) { 
    6.   
  
  
  
  6.         // 此时说明找到了一组 
    7.   
  
  
  
  7.         if (path.size() == nums.size()) { 
    8.   
  
  
  
  8.             result.push_back(path); 
    9.   
  
  
  
  9.             return; 
    10.   
  
  
  
  10.         } 
    11.   
  
  
  
  11.         for (int i = 0; i < nums.size(); i++) { 
    12.   
  
  
  
  12.             // used[i - 1] == true，说明同一树支nums[i - 1]使用过 
    13.   
  
  
  
  13.             // used[i - 1] == false，说明同一树层nums[i - 1]使用过 
    14.   
  
  
  
  14.             // 如果同一树层nums[i - 1]使用过则直接跳过 
    15.   
  
  
  
  15.             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    16.   
  
  
  
  16.                 continue; 
    17.   
  
  
  
  17.             } 
    18.   
  
  
  
  18.             if (used[i] == false) { 
    19.   
  
  
  
  19.                 used[i] = true; 
    20.   
  
  
  
  20.                 path.push_back(nums[i]); 
    21.   
  
  
  
  21.                 backtracking(nums, used); 
    22.   
  
  
  
  22.                 path.pop_back(); 
    23.   
  
  
  
  23.                 used[i] = false; 
    24.   
  
  
  
  24.             } 
    25.   
  
  
  
  25.         } 
    26.   
  
  
  
  26.     } 
    27.   
  
  
  
  27. public: 
    28.   
  
  
  
  28.     vector> permuteUnique(vector& nums) { 
    29.   
  
  
  
  29.         result.clear(); 
    30.   
  
  
  
  30.         path.clear(); 
    31.   
  
  
  
  31.         sort(nums.begin(), nums.end()); // 排序 
    32.   
  
  
  
  32.         vector used(nums.size(), false); 
    33.   
  
  
  
  33.         backtracking(nums, used); 
    34.   
  
  
  
  34.         return result; 
    35.   
  
  
  
  35.     } 
    36.   
  
  
  
  36. }; 
    37.

拓展

大家发现，去重最为关键的代码为：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高!

这么说是不是有点抽象?

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)，的树形结构如下：

全排列II2

树枝上去重(used[i - 1] == true)的树型结构如下：

全排列II

大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

总结

这道题其实还是用了我们之前讲过的去重思路，但有意思的是，去重的代码中，这么写：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

和这么写：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

都是可以的，这也是很多同学做这道题目困惑的地方，知道used[i - 1] == false也行而used[i - 1] == true也行，但是就想不明白为啥。

所以我通过举[1,1,1]的例子，把这两个去重的逻辑分别抽象成树形结构，大家可以一目了然：为什么两种写法都可以以及哪一种效率更高!

是不是豁然开朗了!!

本文转载自微信公众号「代码随想录」，可以通过以下二维码关注。转载本文请联系代码随想录公众号。

网页名称：排列问题也要去重了！
路径分享：http://www.csdahua.cn/qtweb/news47/395997.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

自适应网站知识

分类信息网站

品牌网站建设　　 　app软件定制开发　　 　成都网站设计　　 　温江服务器托管　　 　成都酒店服定制　　 　网站空间　　 　全网营销　　 　吉安网站建设　　 　品牌网站定制　　 　搜索引擎优化　　 　门户网站建设方案　　 　成都做网站　　 　成都网站建设　　 　节能环保网站建设方案　　 　宜宾网站设计　　 　成都西信服务器托管　　 　app制作　　 　微商城开发　　 　成都雪糕加盟　　 　保温橡塑管