当前位置： 首页 > article >正文

刷题记录 回溯算法-16：47. 全排列 II

article 2025/1/18 14:50:21

题目：47. 全排列 II

给定一个可包含重复数字的序列 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

甚至返回命令可以省略

一、模式识别

1.排列问题

与组合问题完全不同，

如果说组合问题像是差额选举，排列问题则更像是等额选举

需要考虑的要素：

①搜索集的大小与路径的长度相等，

②考虑顺序

③每个数使用一次

对应的，排列问题的解决思路：

①创建一个与搜索集等长的盒子，

②将搜索集一个一个放入盒子中 

③控制搜索集，限制每个元素只使用一次

2.搜索集

nums 中的所有整数 可包含重复数字，需要去重

然而排列问题需要列举所有排列，层间不能顺序访问

所以排列问题和组合问题的去重逻辑与组合问题有所不同 

组合问题常用的去重逻辑是主函数排序数组，回溯递归函数层内检测相邻的元素的层内去重（代码随想录中的树层上去重）：

if i > 0 and candidates[i] == candidates[i - 1] and used[i - 1]:
                continue

由于排列问题层内也是顺序访问，因此可以用类似的逻辑实现去重：

if i > start_idx and candidates[i] == candidates[i - 1]:
                continue

但由于组合问题的路径长度与搜索集长度相等，且层间访问顺序任意，

所以存在检测路径元素和当前元素去重的倒序去重（代码随想录中的树枝上去重）方法

先给出代码，具体的去重逻辑细节后续详述

二、代码实现

代码实现和46. 全排列类似，详见刷题记录 回溯算法-15：46. 全排列-CSDN博客

 但与之不同的是，不考虑去重则有标记数组（常用）、集合和原数组换位三种实现方式，

但考虑去重后第三种方式原数组换位难以实现，具体原因后面详述

 1.标记数组（常用）

同层去重

连续的重复元素时保证只有第一个元素被访问，

判断visited为False表示这是同层元素，否则为已经放入路径盒子path中的元素

class Solution:
    def backtracking(self, nums, visited, path, ans):
        if len(path) == len(nums):
            ans.append(path[:])
            # return
            
        for i, ch in enumerate(nums):
            if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]):
                continue
            path.append(ch)
            visited[i] = True
            self.backtracking(nums, visited, path, ans)
            path.pop()
            visited[i] = False
            
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        visited = [False] * len(nums)
        nums.sort()
        self.backtracking(nums, visited, [], ans)
        return ans

 倒序去重

class Solution:
    def backtracking(self, nums, visited, path, ans):
        if len(path) == len(nums):
            ans.append(path[:])
            # return
            
        for i, ch in enumerate(nums):
            if visited[i] or (i > 0 and nums[i] == nums[i - 1] and visited[i - 1]):
                continue
            path.append(ch)
            visited[i] = True
            self.backtracking(nums, visited, path, ans)
            path.pop()
            visited[i] = False
            
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        visited = [False] * len(nums)
        nums.sort()
        self.backtracking(nums, visited, [], ans)
        return ans

2.集合

同层去重

连续的重复元素时保证只有第一个元素被访问，

用unused集合记录哪些元素已经被访问，即unused集合内的元素为同层的元素，否则为已访问

class Solution:
    def backtracking(self, nums, unused, path, ans):
        if len(path) == len(nums):
            ans.append(path[:])
            # return
            
        for i, ch in enumerate(nums):
            if not i in unused or (i > 0 and nums[i] == nums[i - 1] and (i - 1) in unused):
                continue
            path.append(ch)
            unused.remove(i)
            self.backtracking(nums, unused, path, ans)
            path.pop()
            unused.add(i)
            
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        self.backtracking(nums, set(range(len(nums))), [], ans)
        return ans

倒序去重

class Solution:
    def backtracking(self, nums, unused, path, ans):
        if len(path) == len(nums):
            ans.append(path[:])
            # return
            
        for i, ch in enumerate(nums):
            if not i in unused or (i > 0 and nums[i] == nums[i - 1] and not (i - 1) in unused):
                continue
            path.append(ch)
            unused.remove(i)
            self.backtracking(nums, unused, path, ans)
            path.pop()
            unused.add(i)
            
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        self.backtracking(nums, set(range(len(nums))), [], ans)
        return ans

 实测发现基于集合的实现确实会增大计算开销

三、去重逻辑

1.排列问题如何实现同层去重？

先看排列问题中去重实现的对应命令行：

if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]):
                continue

能发现去重的实现关键在于visited数组的使用，那visited数组的作用是什么呢？

实际上，

visited数组中的True表示的是处于路径path中的节点，

visited数组中的False表示的是没有处于path中的节点，也就是当前层内要访问的元素

 再对比组合问题的对应命令行：

if i > start_idx and candidates[i] == candidates[i - 1]:
                continue

会发现组合问题不需要visited数组，

原因在于组合问题层内以及层与层之间都是顺序访问：

层内：

for i in range(start_idx, len(candidates)):

层与层之间：

self.backtracking(candidates, target, i + 1, path, ans)

而排列问题层内是顺序访问，但层与层之间是任意访问

层内：

for i, ch in enumerate(nums):

层与层之间：

self.backtracking(nums, visited, [], ans)

 所以排列问题需要visited数组用true和false表示哪些是已经放入盒子path中的元素，

而组合问题是顺序访问，用指针start_idx指示访问进度，不需要visited数组

因此排列问题的去重实现就是找出层内且与前一个元素（主函数排序后重复元素紧挨）相等的元素

和组合问题类似

2.倒序去重是什么？为啥能用？

层内去重的逻辑很明显，当访问到层内与前一个元素重复的元素时，会跳过该节点，

因此可以说层内去重的实现是保证层内的重复元素中只在该层内只保留第一个元素，

而倒序去重的实现去重的逻辑就是反过来，保证层内的重复元素只保留最后一个元素，

我叫这种方法倒序去重是因为保留的路径中重复元素是倒序排列的，在后面详述原理

在代码随想录中分别叫做树层上去重和树枝上去重

但这一点和代码随想录中说的一样：

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

代码随想录只给出了示例，并没有给出逻辑上的原理。

首先看实现的效果（两种方法的回溯树）：

同层去重（树层上去重），的树形结构如下：

47.全排列II2

倒序去重（树枝上去重）的树型结构如下：

47.全排列II3

能看到

代码逻辑的去重的具体方法是将多个重复的元素铺设在path中（visited[i - 1]为False时不报错），

具体来说，就是同层访问到了重复元素且前一个重复元素位于path中的双重判断：

if visited[i] or (i > 0 and nums[i] == nums[i - 1] and visited[i - 1]):
                continue

唯一能通过去重机制的是重复元素从后往前顺次铺设的路径

但是递归函数内部的for循环决定了层内元素的访问是顺序访问，

访问的时候不知道哪些元素是重复的，

不可能遇到了连续重复元素就自动倒序访问，

所以树枝上去重的低效率来自于

要把所有非倒序访问的path都弃掉后才能访问需要的倒序访问路径的试错机制

而且数组不止存在连续重复元素，还有其他元素，

也就是在访问到连续重复元素前的每一个节点都要走一遍这种低效的试错机制

那能不能不加visited[i - 1]的检测，直接i > 0 and nums[i] == nums[i - 1]呢？

答案是不行，因为这样会导致程序每当遇到重复元素只保留其中的一个，

使得走出的路径path长度小于搜索集，导致没有任何输出

3.倒序去重的方法组合问题能用吗？

答案是不行

从逻辑上看，原因很简单，

组合问题的代码逻辑是层内层间均为顺序访问，

层间不允许程序倒序访问搜索集，所以肯定是实现不了的

以40.组合问题ii的visited数组解法为例：

class Solution:
    def backtracking(self, candidates, target, start_idx, used, path, ans):
        if target == 0:
            ans.append(path[:])
            return
        if target < 0:
            return
        
        for i in range(start_idx, len(candidates)):
            if i > 0 and candidates[i] == candidates[i - 1] and not used[i - 1]:
                continue
            ch = candidates[i]
            target -= ch
            path.append(ch)
            used[i] = True
            self.backtracking(candidates, target, i + 1, used, path, ans)
            used[i] = False
            path.pop()
            target += ch

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        self.backtracking(candidates, target, 0, [0 for _ in candidates], [], ans)
        return ans

如果改成这样：

class Solution:
    def backtracking(self, candidates, target, start_idx, used, path, ans):
        if target == 0:
            ans.append(path[:])
            return
        if target < 0:
            return
        
        for i in range(start_idx, len(candidates)):
            if i > 0 and candidates[i] == candidates[i - 1] and used[i - 1]:
                continue
            ch = candidates[i]
            target -= ch
            path.append(ch)
            used[i] = True
            self.backtracking(candidates, target, i + 1, used, path, ans)
            used[i] = False
            path.pop()
            target += ch

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        self.backtracking(candidates, target, 0, [0 for _ in candidates], [], ans)
        return ans

测试结果：

输入

candidates =

[10,1,2,7,6,1,5]

target =

8

输出

[[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]

预期结果

[[1,1,6],[1,2,5],[1,7],[2,6]]

四、能否使用换位法？ 

我直接给结论吧，估计是不行

直觉上我觉得存在某种方式可以实现，但我探究后发现很有可能不行

首先我测试了同层去重的实现方法：

class Solution:
    def backtracking(self, nums, start_idx, ans):
        if start_idx == len(nums):
            ans.append(nums[:])
            return
            
        for i in range(start_idx, len(nums)):
            if i > start_idx and nums[i] == nums[start_idx]:
                continue
            nums[i], nums[start_idx] = nums[start_idx], nums[i]
            self.backtracking(nums, start_idx + 1, ans)
            nums[i], nums[start_idx] = nums[start_idx], nums[i]
            
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        used = [False] * len(nums)
        self.backtracking(nums, 0, ans)
        return ans

注意，由于i索引元素和start_idx索引元素交换，去重命令行是这样的：

if i > start_idx and nums[i] == nums[start_idx]:
                continue

而不是：

if i > start_idx and nums[i] == nums[i - 1]:
                continue

这个代码在一些诸如[1,1,2]、[1,2,3]和[0,1,0,0,9]输入时都是可行的

但是当面临两组以上重复元素[2,2,1,1]的输入时，

去重机制就失效了：

输入

nums =

[2,2,1,1]

输出

[[1,1,2,2],[1,2,1,2],[1,2,2,1],[1,2,2,1],[1,2,1,2],[2,1,1,2],[2,1,2,1],[2,2,1,1],[2,1,2,1],[2,1,1,2],[2,2,1,1]]

预期结果

[[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]

然后我尝试继续往下探究，我测试了如果添加visited数组，且跟着nums一起换位：

class Solution:
    def backtracking(self, nums, start_idx, ans, used):
        if start_idx == len(nums):
            ans.append(nums[:])
            return
        
        for i in range(start_idx, len(nums)):
            if i > start_idx and nums[i] == nums[start_idx] and not used[start_idx]:
                continue
            nums[i], nums[start_idx] = nums[start_idx], nums[i]
            used[i] = True
            used[i], used[start_idx] = used[start_idx], used[i]
            self.backtracking(nums, start_idx + 1, ans, used)
            nums[i], nums[start_idx] = nums[start_idx], nums[i]
            used[i] = False
            used[i], used[start_idx] = used[start_idx], used[i]
    
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        used = [False] * len(nums)
        self.backtracking(nums, 0, ans, used)
        return ans

行不行呢？不行！先看结果：

输入

nums =

[2,2,1,1]

输出

[[1,1,2,2],[1,2,1,2],[1,2,2,1],[1,2,2,1],[1,2,1,2],[2,1,1,2],[2,1,2,1],[2,2,1,1],[2,1,2,1],[2,1,1,2],[2,2,1,1]]

预期结果

[[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]

什么都没有改变，

原因是回溯树不同节点之间的used数组的换位方式是不同的，

这样比较是毫无意义的，

所以说，换位不仅导致了同层之间的元素顺序的混乱,

还导致了层与层之间的元素顺序混乱.

总结下来，换位会使得无论是回溯树的同层内还是各个节点之间的元素顺序混乱，

也许基于换位解法真的有，但以我的能力确实找不到了


http://www.kler.cn/a/507964.html

相关文章：

  • .Net Core微服务入门全纪录（二）——Consul-服务注册与发现（上）
  • 【Block总结】掩码窗口自注意力 (M-WSA)
  • Linux查看日志命令
  • 阀井可燃气体监测仪，开启地下管网安全新篇章-旭华智能
  • 硬件知识：显示器发展历程介绍
  • 【Flink系列】9. Flink容错机制
  • 从玩具到工业控制--51单片机的跨界传奇【3】
  • NLP入门书籍《掌握NLP：从基础到大语言模型》免费下载pdf
  • MySQL的日期时间类型
  • 《汽车维修技师》是什么级别的期刊？是正规期刊吗？能评职称吗？
  • Vue.js组件开发-实现后端返回二进制文件在浏览器自动下载
  • 基于R语言的现代贝叶斯统计学方法（贝叶斯参数估计、贝叶斯回归、贝叶斯计算实践过程
  • 如何通俗易懂的理解 html js css
  • idea 如何安装 github copilot
  • WPF实现动态四宫格布局
  • 灰度发布、金丝雀部署与蓝绿部署：软件发布的三把利剑
  • Redis | 第6章 事件与客户端《Redis设计与实现》
  • Ubuntu 部署Docker + Dify,遇到的坑, 最新亲测镜像
  • 如何在亚马逊云科技上大幅降低无服务器网页应用冷启动时间（上篇）
  • 在Mac m2系统下安装InSAR软件isce2
  • Python根据图片生成学生excel成绩表
  • [创业之路-254]：《华为数字化转型之道》-1-华为是一个由客户需求牵引、高度数字化、高度智能化、由无数个闭环流程组成的价值创造、评估、分配系统。
  • 学习微信小程序的下拉列表控件-picker
  • NC65增加按钮打开其他单据
  • DX12 快速教程(3) —— 画矩形
  • Java 数据结构 队列之双端队列 常用方法 示例代码 及其实现